Tutorial
Tutorial is loading...
Solution (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
const int INF = int(2e9) + 99;
int n, x, y, d;
int dist(int x, int y){
return (abs(x - y) + (d - 1)) / d;
}
int main() {
int t;
cin >> t;
for(int i = 0; i < t; ++i){
cin >> n >> x >> y >> d;
int len = abs(x - y);
int res = INF;
if(len % d == 0)
res = min(res, dist(x, y));
len = y - 1;
if(len % d == 0)
res = min(res, dist(x, 1) + dist(1, y));
len = n - y;
if(len % d == 0)
res = min(res, dist(x, n) + dist(n, y));
if(res == INF)
res = -1;
cout << res << endl;
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main() {
cin >> n >> s;
vector <int> l(n), r(n);
for(int i = 0; i < n; ++i){
if(s[i] == 'G'){
l[i] = 1;
if(i > 0) l[i] += l[i - 1];
}
}
for(int i = n - 1; i >= 0; --i){
if(s[i] == 'G'){
r[i] = 1;
if(i + 1 < n) r[i] += r[i + 1];
}
}
int res = 0;
int cntG = 0;
for(int i = 0; i < n; ++i)
cntG += s[i] == 'G';
for(int i = 0; i < n; ++i){
if(s[i] == 'G') continue;
int nres = 1;
if(i > 0) nres += l[i - 1];
if(i + 1 < n) nres += r[i + 1];
res = max(res, nres);
}
res = min(res, cntG);
if(cntG == n) res = cntG;
cout << res << endl;
return 0;
}
1082C - Multi-Subject Competition
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
int n, m;
vector<int> s, r;
inline bool read() {
if(!(cin >> n >> m))
return false;
s.assign(n, 0);
r.assign(n, 0);
fore(i, 0, n) {
assert(cin >> s[i] >> r[i]);
s[i]--;
}
return true;
}
vector< vector<int> > subs;
inline void solve() {
subs.assign(m + 1, vector<int>());
fore(i, 0, n)
subs[s[i]].push_back(r[i]);
fore(id, 0, sz(subs)) {
sort(subs[id].begin(), subs[id].end());
reverse(subs[id].begin(), subs[id].end());
}
vector<int> mx(n + 5, 0);
fore(id, 0, sz(subs)) {
int curSum = 0;
fore(i, 0, sz(subs[id])) {
curSum += subs[id][i];
if(curSum < 0)
break;
mx[i + 1] += curSum;
}
}
cout << *max_element(mx.begin(), mx.end()) << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
1082D - Maximum Diameter Graph
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 1000 + 7;
int n;
int a[N];
int main() {
scanf("%d", &n);
forn(i, n)
scanf("%d", &a[i]);
int sum = 0;
forn(i, n)
sum += a[i];
if (sum < 2 * n - 2){
puts("NO");
return 0;
}
vector<int> ones;
forn(i, n) if (a[i] == 1){
a[i] = 0;
ones.push_back(i);
}
int t = ones.size();
int dm = (n - t) - 1 + min(2, t);
printf("YES %d\n%d\n", dm, n - 1);
int lst = -1;
if (!ones.empty()){
lst = ones.back();
ones.pop_back();
}
forn(i, n){
if (a[i] > 1){
if (lst != -1){
--a[lst];
--a[i];
printf("%d %d\n", lst + 1, i + 1);
}
lst = i;
}
}
for (int i = n - 1; i >= 0; --i){
while (!ones.empty() && a[i] > 0){
--a[i];
printf("%d %d\n", i + 1, ones.back() + 1);
ones.pop_back();
}
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
const int INF = int(1e9);
int n, c;
vector<int> a;
inline bool read() {
if(!(cin >> n >> c))
return false;
a.assign(n, 0);
fore(i, 0, n)
assert(scanf("%d", &a[i]) == 1);
return true;
}
vector<int> cntC;
int getCnt(int l, int r) {
return cntC[r] - cntC[l];
}
vector< vector<int> > segs;
vector<int> lst;
int maxSegment(const vector<int> &s) {
int mx = -INF;
int bal = 0;
fore(i, 0, sz(s)) {
bal = max(0, bal + s[i]);
mx = max(mx, bal);
}
return mx;
}
inline void solve() {
cntC.assign(n + 1, 0);
fore(i, 0, n)
cntC[i + 1] = cntC[i] + (a[i] == c);
int cntDif = *max_element(a.begin(), a.end()) + 1;
segs.assign(cntDif, vector<int>());
lst.assign(cntDif, -1);
fore(i, 0, n) {
segs[a[i]].push_back(-getCnt(lst[a[i]] + 1, i));
lst[a[i]] = i;
segs[a[i]].push_back(1);
}
fore(v, 0, cntDif)
segs[v].push_back(-getCnt(lst[v] + 1, n));
int ans = 0;
fore(v, 0, cntDif) {
if(v == c) continue;
ans = max(ans, maxSegment(segs[v]));
}
cout << getCnt(0, n) + ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 500 + 7;
const int M = 11;
const int INF = 1e9;
struct node{
int nxt[10];
int cnt;
node(){
memset(nxt, -1, sizeof(nxt));
cnt = 0;
}
};
node trie[N];
int cnt;
int h[N];
void add(string s, int m){
int cur = 0;
forn(i, s.size()){
int c = s[i] - '0';
if (trie[cur].nxt[c] == -1){
trie[cur].nxt[c] = cnt;
h[cnt] = h[cur] + 1;
++cnt;
}
cur = trie[cur].nxt[c];
}
trie[cur].cnt += m;
}
int n, k;
int dp[N][M][N];
int dp2[N][M][N][M];
int calc(int x, int rem, int k){
if (dp[x][rem][k] != -1)
return dp[x][rem][k];
vector<int> ch;
forn(i, 10) if (trie[x].nxt[i] != -1)
ch.push_back(trie[x].nxt[i]);
dp[x][rem][k] = INF;
if (rem > 0)
dp[x][rem][k] = min(dp[x][rem][k], calc(x, rem - 1, x));
dp2[x][rem][k][ch.size()] = 0;
for (int i = int(ch.size()) - 1; i >= 0; --i) forn(z, rem + 1)
dp2[x][rem][k][i] = min(dp2[x][rem][k][i], calc(ch[i], z, k) + dp2[x][rem - z][k][i + 1]);
dp[x][rem][k] = min(dp[x][rem][k], dp2[x][rem][k][0] + (h[x] - h[k]) * trie[x].cnt);
return dp[x][rem][k];
}
int main() {
trie[0] = node();
cnt = 1;
cin >> n >> k;
forn(i, n){
string s;
int m;
cin >> s >> m;
add(s, m);
}
memset(dp, -1, sizeof(dp));
forn(i, N) forn(j, M) forn(l, N) forn(t, M)
dp2[i][j][l][t] = INF;
int ans = calc(0, k, 0);
cout << ans << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
typedef long long li;
const int N = 2009;
const int INF = int(1e9) + 777;
struct edge{
int to, f, c;
edge () {}
edge (int to, int f, int c) : to(to), f(f), c(c) {}
};
int n, m;
int s, t;
vector<edge> edges;
vector <int> g[N];
int u[N], cu;
void addEdge(int v, int to, int cap){
g[v].push_back(edges.size());
edges.push_back(edge(to, 0, cap));
g[to].push_back(edges.size());
edges.push_back(edge(v, 0, 0));
}
int dfs(int v, int need){
if(v == t) return need;
u[v] = cu;
for(auto to : g[v]){
edge &e = edges[to];
if(u[e.to] != cu && e.c - e.f >= need){
int add = dfs(e.to, need);
if(add > 0){
edges[to].f += add;
edges[to ^ 1].f -= add;
return add;
}
}
}
return 0;
}
li enlarge(int k){
li res = 0;
while(true){
++cu;
int add = dfs(s, k);
res += add;
if(add == 0) break;
}
return res;
}
li maxFlow(){
li flow = 0;
for(int k = (1 << 29); k > 0; k >>= 1){
flow += enlarge(k);
}
return flow;
}
int main() {
//freopen("input.txt", "r", stdin);
int nn, mm;
cin >> nn >> mm;
n = nn + mm + 5;
m = nn + mm + mm + mm + 5;
s = n - 1, t = n - 2;
for(int i = 0; i < nn; ++i){
int a;
cin >> a;
addEdge(i + mm, t, a);
}
li sum = 0;
for(int i = 0; i < mm; ++i){
int u, v, w;
cin >> u >> v >> w;
--u, --v;
sum += w;
addEdge(s, i, w);
addEdge(i, u + mm, INF);
addEdge(i, v + mm, INF);
}
li fl = maxFlow();
cout << sum - fl << endl;
return 0;
}