oj.uz

Submission #912369

# Submission time Handle Problem Language Result Execution time Memory
912369 2024-01-19T10:25:10 Z vjudge1 Potatoes and fertilizers (LMIO19_bulves) C++17
54 / 100
 872 ms 24304 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 100;
int n, m;
long long dp[60300];
long long d[60300];
long long A, B;
int a[maxn], b[maxn];
long long p[maxn];
long long rp[maxn];
int main() {
    cin >> n;
    long long cur = 0;
    for(int i=1; i<=n; i++) {
        cin >> a[i] >> b[i];
        A += a[i];
        B += b[i];
        p[i] = p[i-1] + abs(A-B);
    }
    long long ca = 0, cb = 0;
    for(int i = n; i >= 1; i--) {
        rp[i] = rp[i+1] + abs(ca-cb);
        ca += a[i];
        cb += b[i];
    }

    if(A <= 30000) {
        for(int j = 0; j <= 2*A; j++) {
            dp[j] = 1e18;
        }
        dp[A] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= 2 * A; j++) {
                d[j] = dp[j] + abs(j-A);
                dp[j] = 1e18;
            }
            for(int j = 0; j <= 2 * A; j++) {
                int k = j + a[i] - b[i];
                if(k >= 0 && k <= 2 * A) {
                    dp[k] = min(dp[k], d[j]);
                }
            }
            for(int j = 2 * A-1; j >= 0; j--) {
                dp[j] = min(dp[j+1], dp[j]);
            }
        }
        cout << dp[A];
    } else {
        long long ans = 1e18;
        for(int i = 1; i <= n; i++) {
            ans = min(ans, p[i-1] + rp[i]);
        }
        cout << ans << "\n";
    }
}

Compilation message

bulves.cpp: In function 'int main()':
bulves.cpp:13:15: warning: unused variable 'cur' [-Wunused-variable]
   13 |     long long cur = 0;
      |               ^~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 15 ms 7324 KB Output is correct
5 Correct 29 ms 7976 KB Output is correct
6 Correct 105 ms 11348 KB Output is correct
7 Correct 221 ms 17536 KB Output is correct
8 Correct 177 ms 17520 KB Output is correct
9 Correct 160 ms 17488 KB Output is correct
10 Correct 120 ms 17748 KB Output is correct
11 Correct 134 ms 17492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 15 ms 7324 KB Output is correct
5 Correct 29 ms 7976 KB Output is correct
6 Correct 105 ms 11348 KB Output is correct
7 Correct 221 ms 17536 KB Output is correct
8 Correct 177 ms 17520 KB Output is correct
9 Correct 160 ms 17488 KB Output is correct
10 Correct 120 ms 17748 KB Output is correct
11 Correct 134 ms 17492 KB Output is correct
12 Correct 53 ms 10576 KB Output is correct
13 Correct 128 ms 15952 KB Output is correct
14 Correct 229 ms 24304 KB Output is correct
15 Correct 177 ms 22360 KB Output is correct
16 Correct 161 ms 21724 KB Output is correct
17 Correct 119 ms 19808 KB Output is correct
18 Correct 14 ms 4620 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 14 ms 4620 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 98 ms 4864 KB Output is correct
6 Correct 441 ms 5516 KB Output is correct
7 Correct 872 ms 5716 KB Output is correct
8 Correct 437 ms 4956 KB Output is correct
9 Correct 250 ms 4700 KB Output is correct
10 Correct 868 ms 5520 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 98 ms 4864 KB Output is correct
6 Correct 441 ms 5516 KB Output is correct
7 Correct 872 ms 5716 KB Output is correct
8 Correct 437 ms 4956 KB Output is correct
9 Correct 250 ms 4700 KB Output is correct
10 Correct 868 ms 5520 KB Output is correct
11 Correct 14 ms 4620 KB Output is correct
12 Incorrect 2 ms 4456 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 98 ms 4864 KB Output is correct
6 Correct 441 ms 5516 KB Output is correct
7 Correct 872 ms 5716 KB Output is correct
8 Correct 437 ms 4956 KB Output is correct
9 Correct 250 ms 4700 KB Output is correct
10 Correct 868 ms 5520 KB Output is correct
11 Correct 15 ms 7324 KB Output is correct
12 Correct 29 ms 7976 KB Output is correct
13 Correct 105 ms 11348 KB Output is correct
14 Correct 221 ms 17536 KB Output is correct
15 Correct 177 ms 17520 KB Output is correct
16 Correct 160 ms 17488 KB Output is correct
17 Correct 120 ms 17748 KB Output is correct
18 Correct 134 ms 17492 KB Output is correct
19 Correct 53 ms 10576 KB Output is correct
20 Correct 128 ms 15952 KB Output is correct
21 Correct 229 ms 24304 KB Output is correct
22 Correct 177 ms 22360 KB Output is correct
23 Correct 161 ms 21724 KB Output is correct
24 Correct 119 ms 19808 KB Output is correct
25 Incorrect 2 ms 4456 KB Output isn't correct
26 Halted 0 ms 0 KB -