oj.uz

Submission #1085324

# Submission time Handle Problem Language Result Execution time Memory
1085324 2024-09-08T00:41:53 Z trMatherz Potatoes and fertilizers (LMIO19_bulves) C++17
34 / 100
 210 ms 262144 KB 
#include <iostream> //cin, cout


// #include <fstream>
// std::ifstream cin ("tallbarn.in");
// std::ofstream cout ("tallbarn.out");





// includes
#include <cmath> 
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <complex>


//usings 
using namespace std;
using namespace __gnu_pbds;


// misc
#define ll long long
#define ld long double
#define pb push_back
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; }
typedef uint64_t hash_t;

// vectors
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vppipi vector<pair<int, pair<int, int>>>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vpll vector<pair<ll, ll>>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define sz(x) (int)x.size()
#define rz resize
#define all(x) x.begin(), x.end()
#define vc vector<char>
#define vvc vector<vc>


// pairs
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define f first
#define s second

// sets
#define si set<int>
#define sl set<ll>
#define ss set<string>
#define in insert
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// maps
#define mii map<int, int>
#define mll map<ll, ll>

// loops
#define FR(x, z, y) for (int x = z; x < y; x++)
#define FRE(x, z, y) FR(x, z, y + 1)
#define F(x, y) FR(x, 0, y)
#define FE(x, y) F(x, y + 1)
#define A(x, y) for(auto &x : y)


int main(){
    int n; cin >> n; 
    vl a, b;
    int suma = 0, sumb = 0;
    F(i, n) {
        int x; cin >> x; a.pb(x); suma += x;
        cin >> x; b.pb(x); sumb += x; 
    }
    vvl dp(n + 1, vl(suma - sumb + 1, 0));
    ll cur = 0;
    F(i, n){
        cur += a[i] - b[i]; 
        F(j, suma - sumb + 1) {
            dp[i + 1][j] = dp[i][j] + abs(cur - j);
            if(j != 0) emin(dp[i + 1][j], dp[i + 1][j - 1]); 
        }
    }
    // A(u, dp){
    //     A(l, u) cout << l << " ";
    //     cout << endl;
    // }
    cout << dp[n][suma - sumb]; 
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 14 ms 3896 KB Output is correct
5 Correct 30 ms 7460 KB Output is correct
6 Correct 105 ms 17836 KB Output is correct
7 Correct 203 ms 35492 KB Output is correct
8 Correct 173 ms 35484 KB Output is correct
9 Correct 163 ms 35480 KB Output is correct
10 Correct 109 ms 35424 KB Output is correct
11 Correct 113 ms 35528 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 14 ms 3896 KB Output is correct
5 Correct 30 ms 7460 KB Output is correct
6 Correct 105 ms 17836 KB Output is correct
7 Correct 203 ms 35492 KB Output is correct
8 Correct 173 ms 35484 KB Output is correct
9 Correct 163 ms 35480 KB Output is correct
10 Correct 109 ms 35424 KB Output is correct
11 Correct 113 ms 35528 KB Output is correct
12 Correct 55 ms 9148 KB Output is correct
13 Correct 130 ms 25564 KB Output is correct
14 Correct 210 ms 42392 KB Output is correct
15 Correct 182 ms 40440 KB Output is correct
16 Correct 160 ms 39836 KB Output is correct
17 Correct 116 ms 37528 KB Output is correct
18 Correct 1 ms 604 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 13 ms 16196 KB Output is correct
6 Correct 40 ms 59228 KB Output is correct
7 Runtime error 114 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 13 ms 16196 KB Output is correct
6 Correct 40 ms 59228 KB Output is correct
7 Runtime error 114 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 13 ms 16196 KB Output is correct
6 Correct 40 ms 59228 KB Output is correct
7 Runtime error 114 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -