oj.uz

Submission #414576

# Submission time Handle Problem Language Result Execution time Memory
414576 2021-05-30T16:43:18 Z Aldas25 Potatoes and fertilizers (LMIO19_bulves) C++14
54 / 100
 153 ms 32716 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;

const int MAXN = 500100, MAXK = 30;
//const ll MOD = 998244353;
const ll INF = 4e18;
const ld PI = asin(1) * 2;

int n;
ll a[MAXN], b[MAXN], dif[MAXN], pref[MAXN];

ll dp[2][31000];

int main()
{
    FAST_IO;

    cin >> n;
    FOR(i, 1, n) cin >> a[i] >> b[i];

    FOR(i, 1, n) {
        dif[i] = a[i]-b[i];
        pref[i] = pref[i-1] + dif[i];
    }

    ll mx = pref[n];

    FOR(i, 1, n) FOR(j, 0, mx) {
        bool b = i%2;
        if (j > 0) dp[b][j] = dp[b][j-1];
        else dp[b][j] = INF;

        dp[b][j] = min(dp[b][j], dp[!b][j] + abs(j - pref[i]));
    }

    cout << dp[n%2][mx] << "\n";

    return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 10 ms 2224 KB Output is correct
5 Correct 19 ms 4072 KB Output is correct
6 Correct 58 ms 11480 KB Output is correct
7 Correct 116 ms 22712 KB Output is correct
8 Correct 103 ms 20820 KB Output is correct
9 Correct 101 ms 20080 KB Output is correct
10 Correct 81 ms 17904 KB Output is correct
11 Correct 85 ms 17920 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 10 ms 2224 KB Output is correct
5 Correct 19 ms 4072 KB Output is correct
6 Correct 58 ms 11480 KB Output is correct
7 Correct 116 ms 22712 KB Output is correct
8 Correct 103 ms 20820 KB Output is correct
9 Correct 101 ms 20080 KB Output is correct
10 Correct 81 ms 17904 KB Output is correct
11 Correct 85 ms 17920 KB Output is correct
12 Correct 34 ms 5856 KB Output is correct
13 Correct 85 ms 13692 KB Output is correct
14 Correct 117 ms 22708 KB Output is correct
15 Correct 102 ms 20800 KB Output is correct
16 Correct 100 ms 20172 KB Output is correct
17 Correct 82 ms 17872 KB Output is correct
18 Correct 1 ms 460 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 9 ms 332 KB Output is correct
6 Correct 30 ms 452 KB Output is correct
7 Correct 153 ms 652 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 13 ms 488 KB Output is correct
10 Correct 14 ms 460 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 9 ms 332 KB Output is correct
6 Correct 30 ms 452 KB Output is correct
7 Correct 153 ms 652 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 13 ms 488 KB Output is correct
10 Correct 14 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Runtime error 33 ms 32716 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 9 ms 332 KB Output is correct
6 Correct 30 ms 452 KB Output is correct
7 Correct 153 ms 652 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 13 ms 488 KB Output is correct
10 Correct 14 ms 460 KB Output is correct
11 Correct 10 ms 2224 KB Output is correct
12 Correct 19 ms 4072 KB Output is correct
13 Correct 58 ms 11480 KB Output is correct
14 Correct 116 ms 22712 KB Output is correct
15 Correct 103 ms 20820 KB Output is correct
16 Correct 101 ms 20080 KB Output is correct
17 Correct 81 ms 17904 KB Output is correct
18 Correct 85 ms 17920 KB Output is correct
19 Correct 34 ms 5856 KB Output is correct
20 Correct 85 ms 13692 KB Output is correct
21 Correct 117 ms 22708 KB Output is correct
22 Correct 102 ms 20800 KB Output is correct
23 Correct 100 ms 20172 KB Output is correct
24 Correct 82 ms 17872 KB Output is correct
25 Runtime error 33 ms 32716 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -