oj.uz

Submission #153047

# Submission time Handle Problem Language Result Execution time Memory
153047 2019-09-11T15:31:52 Z Mercenary Popeala (CEOI16_popeala) C++14
100 / 100
 524 ms 219248 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 2e4 + 5;

int dp[maxn][51] , dp1[maxn][51][51];
int n , s , t;
int pre[51][maxn];
vector<int> v[maxn];

int point[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    fill_n(&dp[0][0],maxn*51,2e9);
    fill_n(&dp1[0][0][0],maxn*51*51,2e9);
    cin >> n >> t >> s;
    for(int i = 1 ; i <= t ; ++i){
        cin >> point[i];
        point[i] += point[i - 1];
    }
    for(int i = 0 ; i < n ; ++i){
        string s;cin >> s;
        for(int j = 1 ; j <= t ; ++j){
            if(s[j - 1] == '1')pre[i][j] = pre[i][j - 1];
            else pre[i][j] = j;
            v[j].pb(pre[i][j]);
        }
    }
    dp[0][0] = 0;
    for(int i = 0 ; i <= n ; ++i){
        dp1[0][0][i] = 0;
    }
    for(int i = 1 ; i <= t ; ++i){
        v[i].pb(i);
        sort(v[i].begin(),v[i].end(),greater<int>());
        for(int j = 1 ; j <= s ; ++j){
            for(int c = 0 ; c <= n ; ++c){
//                    cout << j << " " << id << " " << dp[id - 1][j - 1] << endl;
                if(v[i][c] > 0)dp[i][j] = min(dp[i][j] , dp1[v[i][c] - 1][j - 1][n - c] + (n - c) * point[i]);

            }
//            cout << dp[i][j] << " \n"[j == s];
        }
//        break;
        for(int j = 0 ; j <= s ; ++j){
            for(int c = 0 ; c <= n ; ++c){
                dp1[i][j][c] = min((ll)dp1[i - 1][j][c] , (ll)dp[i][j] - c * point[i]);
            }
        }
    }
    for(int j = 1 ; j <= s ; ++j){
        cout << dp[t][j] << '\n';
    }
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 208504 KB Output is correct
2 Correct 182 ms 208668 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 208912 KB Output is correct
2 Correct 192 ms 208860 KB Output is correct
3 Correct 213 ms 208908 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 209748 KB Output is correct
2 Correct 233 ms 210296 KB Output is correct
3 Correct 251 ms 210836 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 208504 KB Output is correct
2 Correct 182 ms 208668 KB Output is correct
3 Correct 190 ms 208912 KB Output is correct
4 Correct 192 ms 208860 KB Output is correct
5 Correct 213 ms 208908 KB Output is correct
6 Correct 219 ms 209748 KB Output is correct
7 Correct 233 ms 210296 KB Output is correct
8 Correct 251 ms 210836 KB Output is correct
9 Correct 294 ms 212180 KB Output is correct
10 Correct 325 ms 213280 KB Output is correct
11 Correct 508 ms 218904 KB Output is correct
12 Correct 522 ms 219136 KB Output is correct
13 Correct 524 ms 219032 KB Output is correct
14 Correct 515 ms 219084 KB Output is correct
15 Correct 516 ms 219248 KB Output is correct