oj.uz

Submission #76538

# Submission time Handle Problem Language Result Execution time Memory
76538 2018-09-14T14:45:08 Z georgerapeanu Popeala (CEOI16_popeala) C++11
100 / 100
 1743 ms 16756 KB 
#include <cstdio>
#include <algorithm>
#include <deque>
 
using namespace std;
 
const int TMAX = 2e4;
const int NMAX = 50;
const int SMAX = 50;
const int INF = (1 << 29);
 
FILE *f = stdin;
FILE *g = stdout;
 
int t,n,s;
 
int points[TMAX + 5];
int preffix_sum[TMAX + 5];
 
char results[NMAX + 5][TMAX + 5];
int valid_from[NMAX + 5][TMAX + 5];
 
int dp[SMAX + 5][TMAX + 5];
 
int ant[NMAX + 5];
int nxt[NMAX + 5];
 
int st[NMAX + 5];
int dr[NMAX + 5];
deque< pair<int,int> > segment[NMAX + 5];
 
int main(){
 
    fscanf(f,"%d %d %d\n",&n,&t,&s);
 
    for(int i = 1;i <= t;i++){
        fscanf(f,"%d",&points[i]);
        preffix_sum[i] = preffix_sum[i - 1] + points[i];
    }
     
    fscanf(f,"\n");
 
    for(int i = 1;i <= n;i++){
        fgets(results[i] + 1,TMAX + 5,f);
    }
 
    for(int i = 1;i <= n;i++){
        valid_from[i][0] = 1;
        for(int j = 1;j <= t;j++){
            valid_from[i][j] = (results[i][j] == '1' ? valid_from[i][j - 1]:j + 1);
        }
    }
 
    for(int j = 1;j <= t;j++){
        dp[0][j] = INF;
    }
     
    for(int i = 1;i <= s;i++){
 
        for(int j = 0;j <= n;j++){
            nxt[j] = j + 1;
            ant[j] = j - 1;
            st[j] = 1;
            dr[j] = 1;
            segment[j].clear(); 
        }
 
        ant[0] = n;
        nxt[n] = 0;
         
        dp[i][0] = INF;
         
        for(int j = 1;j <= t;j++){
            for(int k = 1;k <= n;k++){
                if(valid_from[k][j] != valid_from[k][j - 1]){
                    nxt[ant[k]] = nxt[k];
                    ant[nxt[k]] = ant[k];
 
                    int head = ant[0];
 
                    nxt[k] = nxt[head];
                    ant[k] = head;
 
                    nxt[ant[k]] = k;
                    ant[nxt[k]] = k;
                }
            }
             
            if(j < i){
                dp[i][j] = INF;
                continue;
            }
                                       
            dp[i][j] = INF;
             
            for(int seg = n,nod = ant[0];seg >= 0;seg--,nod = ant[nod]){
				
				int left = valid_from[nod][j];
				int right = (nxt[nod] == 0 ? j + 1:valid_from[nxt[nod]][j]);
				
                while(dr[seg] < right){
                    int cost = dp[i - 1][dr[seg] - 1] - preffix_sum[dr[seg] - 1] * seg;
                    while(segment[seg].size() && segment[seg].back().second >= cost){
                        segment[seg].pop_back();
                    }
                    segment[seg].push_back({dr[seg],cost});
                    dr[seg]++;
                }
                 
                while(st[seg] < left){
                    while(segment[seg].size() && segment[seg].front().first <= st[seg]){
                        segment[seg].pop_front();
                    }
                    st[seg]++;
                }
                 
                if(segment[seg].size()){
                    dp[i][j] = min(dp[i][j],segment[seg].front().second + preffix_sum[j] * seg);
                }
            }
        }   
        fprintf(g,"%d\n",dp[i][t]);
    }
     
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:34:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(f,"%d %d %d\n",&n,&t,&s);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:37:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(f,"%d",&points[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~
popeala.cpp:41:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(f,"\n");
     ~~~~~~^~~~~~~~
popeala.cpp:44:14: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         fgets(results[i] + 1,TMAX + 5,f);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 896 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1432 KB Output is correct
2 Correct 55 ms 1480 KB Output is correct
3 Correct 39 ms 1604 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 2492 KB Output is correct
2 Correct 258 ms 3180 KB Output is correct
3 Correct 331 ms 3648 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 896 KB Output is correct
3 Correct 48 ms 1432 KB Output is correct
4 Correct 55 ms 1480 KB Output is correct
5 Correct 39 ms 1604 KB Output is correct
6 Correct 183 ms 2492 KB Output is correct
7 Correct 258 ms 3180 KB Output is correct
8 Correct 331 ms 3648 KB Output is correct
9 Correct 475 ms 5148 KB Output is correct
10 Correct 755 ms 6584 KB Output is correct
11 Correct 1453 ms 12024 KB Output is correct
12 Correct 1556 ms 13500 KB Output is correct
13 Correct 1631 ms 14544 KB Output is correct
14 Correct 1743 ms 15640 KB Output is correct
15 Correct 1665 ms 16756 KB Output is correct