#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
const int MAXN = 5e5+5, INF = 1e9+50;
const ll INF_L = (ll)1e18+(ll)50000;
int n;
int A[MAXN];
int B[MAXN];
int C[MAXN];
ll S[MAXN];
vector<ll> stan;
vector<vector<ll>> dp;
void solve()
{
cin >> n;
rep(i,n) cin >> A[i] >> B[i];
rep(i,n) C[i] = A[i]-B[i];
S[0] = C[0];
for(int i = 1; i < n; ++i) S[i] = S[i-1] + C[i];
set<ll> fg;
rep(i,n)
{
if(S[i] >= 0 and S[i] <= S[n-1]) fg.insert(S[i]);
}
fg.insert(0);
for(auto it = fg.begin(); it != fg.end(); ++it) stan.pb(*it);
dp.assign(n,{});
rep(i,n) dp[i].assign((int)stan.size(),INF_L);
rep(i,n)
{
ll mn = INF_L;
rep(j,(int)stan.size())
{
if(i > 0) mn = min(mn,dp[i-1][j]);
dp[i][j] = abs(S[i]-stan[j]);
if(i > 0)
{
if(mn == INF_L) dp[i][j] = INF_L;
else dp[i][j] += mn;
}
}
}
ll mn = INF_L;
rep(i,(int)stan.size()) mn = min(mn,dp[n-1][i]);
cout << mn << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
7 ms |
4188 KB |
Output is correct |
5 |
Correct |
13 ms |
7772 KB |
Output is correct |
6 |
Correct |
43 ms |
18828 KB |
Output is correct |
7 |
Correct |
80 ms |
37512 KB |
Output is correct |
8 |
Correct |
72 ms |
37456 KB |
Output is correct |
9 |
Correct |
74 ms |
39764 KB |
Output is correct |
10 |
Correct |
62 ms |
38736 KB |
Output is correct |
11 |
Correct |
60 ms |
38736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
7 ms |
4188 KB |
Output is correct |
5 |
Correct |
13 ms |
7772 KB |
Output is correct |
6 |
Correct |
43 ms |
18828 KB |
Output is correct |
7 |
Correct |
80 ms |
37512 KB |
Output is correct |
8 |
Correct |
72 ms |
37456 KB |
Output is correct |
9 |
Correct |
74 ms |
39764 KB |
Output is correct |
10 |
Correct |
62 ms |
38736 KB |
Output is correct |
11 |
Correct |
60 ms |
38736 KB |
Output is correct |
12 |
Correct |
27 ms |
10592 KB |
Output is correct |
13 |
Correct |
50 ms |
25056 KB |
Output is correct |
14 |
Correct |
92 ms |
41220 KB |
Output is correct |
15 |
Correct |
78 ms |
40300 KB |
Output is correct |
16 |
Correct |
72 ms |
39768 KB |
Output is correct |
17 |
Correct |
89 ms |
38740 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
3 ms |
4956 KB |
Output is correct |
6 |
Correct |
7 ms |
11612 KB |
Output is correct |
7 |
Correct |
34 ms |
59424 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
8 ms |
12380 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
3 ms |
4956 KB |
Output is correct |
6 |
Correct |
7 ms |
11612 KB |
Output is correct |
7 |
Correct |
34 ms |
59424 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
8 ms |
12380 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
18 ms |
31324 KB |
Output is correct |
13 |
Correct |
41 ms |
69200 KB |
Output is correct |
14 |
Correct |
40 ms |
70992 KB |
Output is correct |
15 |
Correct |
42 ms |
71248 KB |
Output is correct |
16 |
Correct |
11 ms |
19288 KB |
Output is correct |
17 |
Correct |
16 ms |
26972 KB |
Output is correct |
18 |
Correct |
13 ms |
21340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
3 ms |
4956 KB |
Output is correct |
6 |
Correct |
7 ms |
11612 KB |
Output is correct |
7 |
Correct |
34 ms |
59424 KB |
Output is correct |
8 |
Correct |
1 ms |
860 KB |
Output is correct |
9 |
Correct |
8 ms |
12380 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
11 |
Correct |
7 ms |
4188 KB |
Output is correct |
12 |
Correct |
13 ms |
7772 KB |
Output is correct |
13 |
Correct |
43 ms |
18828 KB |
Output is correct |
14 |
Correct |
80 ms |
37512 KB |
Output is correct |
15 |
Correct |
72 ms |
37456 KB |
Output is correct |
16 |
Correct |
74 ms |
39764 KB |
Output is correct |
17 |
Correct |
62 ms |
38736 KB |
Output is correct |
18 |
Correct |
60 ms |
38736 KB |
Output is correct |
19 |
Correct |
27 ms |
10592 KB |
Output is correct |
20 |
Correct |
50 ms |
25056 KB |
Output is correct |
21 |
Correct |
92 ms |
41220 KB |
Output is correct |
22 |
Correct |
78 ms |
40300 KB |
Output is correct |
23 |
Correct |
72 ms |
39768 KB |
Output is correct |
24 |
Correct |
89 ms |
38740 KB |
Output is correct |
25 |
Correct |
18 ms |
31324 KB |
Output is correct |
26 |
Correct |
41 ms |
69200 KB |
Output is correct |
27 |
Correct |
40 ms |
70992 KB |
Output is correct |
28 |
Correct |
42 ms |
71248 KB |
Output is correct |
29 |
Correct |
11 ms |
19288 KB |
Output is correct |
30 |
Correct |
16 ms |
26972 KB |
Output is correct |
31 |
Correct |
13 ms |
21340 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Runtime error |
118 ms |
262144 KB |
Execution killed with signal 9 |
34 |
Halted |
0 ms |
0 KB |
- |