oj.uz

Submission #1083433

# Submission time Handle Problem Language Result Execution time Memory
1083433 2024-09-03T06:09:08 Z hqminhuwu Potatoes and fertilizers (LMIO19_bulves) C++14
20 / 100
 129 ms 2644 KB 
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
 
#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
 
template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }
 
const int N = 3e3 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;
 
int n, a[N], b[N];
ll d[N], dp[2][60001];
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef hqm
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif
 
    cin >> n;
 
    assert(n <= 3000);
 
    memset (dp, 63, sizeof dp);
    dp[0][0] = 0;
 
    forr (i, 1, n){
        cin >> a[i] >> b[i];
        d[i] = d[i - 1] + a[i] - b[i];
    }
    
    forr (i, 1, n){
        dp[i & 1][0] = dp[(i - 1) & 1][0];    
        forr (j, 1, 30000){
            dp[i & 1][j] = min (dp[i & 1][j - 1], dp[(i - 1) & 1][j]);
        }
 
        forr (j, 0, 30000){
            dp[i & 1][j] += abs(d[i] - j);
           // cout << dp[i & 1][j] << " ";
        }
        //cout << "\n";
    }
 
    ll ans = oo;
 
    forr (i, 0, d[n]){
        minz(ans, dp[n & 1][i]);
    }
 
    cout << ans;
 
    return 0;
}
/*
 
 
 
*/

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 119 ms 1372 KB Output is correct
3 Correct 119 ms 1372 KB Output is correct
4 Runtime error 1 ms 604 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 119 ms 1372 KB Output is correct
3 Correct 119 ms 1372 KB Output is correct
4 Runtime error 1 ms 604 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 119 ms 1372 KB Output is correct
3 Correct 1 ms 1368 KB Output is correct
4 Correct 40 ms 1372 KB Output is correct
5 Correct 60 ms 1372 KB Output is correct
6 Correct 119 ms 1436 KB Output is correct
7 Correct 120 ms 1372 KB Output is correct
8 Correct 128 ms 1372 KB Output is correct
9 Correct 119 ms 1436 KB Output is correct
10 Correct 129 ms 1368 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 119 ms 1372 KB Output is correct
3 Correct 119 ms 1372 KB Output is correct
4 Correct 1 ms 1368 KB Output is correct
5 Correct 40 ms 1372 KB Output is correct
6 Correct 60 ms 1372 KB Output is correct
7 Correct 119 ms 1436 KB Output is correct
8 Correct 120 ms 1372 KB Output is correct
9 Correct 128 ms 1372 KB Output is correct
10 Correct 119 ms 1436 KB Output is correct
11 Correct 129 ms 1368 KB Output is correct
12 Runtime error 80 ms 2644 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 1372 KB Output is correct
2 Correct 119 ms 1372 KB Output is correct
3 Correct 119 ms 1372 KB Output is correct
4 Correct 1 ms 1368 KB Output is correct
5 Correct 40 ms 1372 KB Output is correct
6 Correct 60 ms 1372 KB Output is correct
7 Correct 119 ms 1436 KB Output is correct
8 Correct 120 ms 1372 KB Output is correct
9 Correct 128 ms 1372 KB Output is correct
10 Correct 119 ms 1436 KB Output is correct
11 Runtime error 1 ms 604 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -