oj.uz

Submission #390910

# Submission time Handle Problem Language Result Execution time Memory
390910 2021-04-17T11:04:44 Z Vladth11 Popeala (CEOI16_popeala) C++14
100 / 100
 299 ms 27056 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 300001;
const ll INF = (1LL << 60);
const ll MOD = 998244353;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 21;

int dp[20001][51];
int n, t, s;
int sum[20001];
int results[51][20001];
int last[51][20001];
int line[20001][51];
int minim[20001][51];
vector <int> pz[20001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> t >> s;
    for(int i = 1; i <= t; i++) {
        cin >> sum[i];
        sum[i] += sum[i - 1];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= t; j++) {
            last[i][j] = last[i][j - 1];
            char c;
            cin >> c;
            results[i][j] = c - '0';
            if(results[i][j] == 0)
                last[i][j] = j;
        }
    }
    for(int i = 0; i <= t; i++) {
        for(int j = 0; j <= s; j++)
            dp[i][j] = 2e9;
    }
    for(int i = 0; i <= t; i++) {
        for(int j = 0; j <= n; j++) {
            minim[i][j] = 2e9;
        }
    }
    for(int i = 1; i <= t; i++){
        for(int j = 1; j <= n; j++){
            pz[i].push_back(last[j][i]);
        }
        sort(pz[i].begin(), pz[i].end());
    }
    dp[0][0] = 0;
    for(int k = 1; k <= s; k++) {
        for(int i = 1; i <= t; i++) {
            for(int j = 0; j <= n; j++) {
                line[i][j] = dp[i - 1][k - 1] - sum[i - 1] * j;
                ///daca luam elementul i cu scor - j
                minim[i][j] = min(minim[i - 1][j], line[i][j]);
            }
        }
        for(int i = 1; i <= t; i++) {
            int scor = n, r = i;
            for(int j = 0; j < pz[i].size(); j++) {
                dp[i][k] = min(dp[i][k], minim[pz[i][j]][j] + sum[i] * j);
            }
            if(pz[i].back() < i)
            dp[i][k] = min(dp[i][k], minim[i][n] + sum[i] * n);
        }
        cout << dp[t][k] << "\n";
    }
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:75:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for(int j = 0; j < pz[i].size(); j++) {
      |                            ~~^~~~~~~~~~~~~~
popeala.cpp:74:17: warning: unused variable 'scor' [-Wunused-variable]
   74 |             int scor = n, r = i;
      |                 ^~~~
popeala.cpp:74:27: warning: unused variable 'r' [-Wunused-variable]
   74 |             int scor = n, r = i;
      |                           ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1744 KB Output is correct
2 Correct 7 ms 1740 KB Output is correct
3 Correct 7 ms 1740 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3904 KB Output is correct
2 Correct 37 ms 4940 KB Output is correct
3 Correct 51 ms 6260 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 7 ms 1744 KB Output is correct
4 Correct 7 ms 1740 KB Output is correct
5 Correct 7 ms 1740 KB Output is correct
6 Correct 27 ms 3904 KB Output is correct
7 Correct 37 ms 4940 KB Output is correct
8 Correct 51 ms 6260 KB Output is correct
9 Correct 94 ms 9388 KB Output is correct
10 Correct 107 ms 11880 KB Output is correct
11 Correct 299 ms 25672 KB Output is correct
12 Correct 256 ms 26948 KB Output is correct
13 Correct 258 ms 27056 KB Output is correct
14 Correct 248 ms 26948 KB Output is correct
15 Correct 262 ms 27056 KB Output is correct