oj.uz

Submission #245147

# Submission time Handle Problem Language Result Execution time Memory
245147 2020-07-05T15:36:02 Z m3r8 Toll (BOI17_toll) C++14
7 / 100
 3000 ms 34920 KB 
#include <stdio.h>


#define N 100100

int bst[N][17][5];
int nm[N][17][5];
int adj[N][5];

int k,n;
int solve(int st, int en){
  int mx = -1;
  if(st == en)return 0;  
  if(st/k == en/k)return -1;
  for(int i = 15;i>=0;i--){
    if(nm[st][i][0]/k <= en/k){
      for(int j = 0;j<k;j++){
        int tmp = solve(nm[st][i][j],en);  
        if(tmp != -1){
          if(bst[st][i][j] != -1){
            if(mx == -1 || mx > bst[st][i][j] + tmp){
              mx = bst[st][i][j] + tmp;  
            };
          };  
        };
      };
      break;
    };
  };
  return mx;
};

int calc(int st, int p, int jk){
  if(st > n){
    return -1;  
  };
  if(bst[st][p][jk])return bst[st][p][jk];  
  if(p == 0){
    if(adj[st][jk])bst[st][p][jk] = adj[st][jk];  
    else bst[st][p][jk] = -1;
    nm[st][p][jk] = (st/k + 1)*k + jk;
    return bst[st][p][jk];
  }else{
    int mx = -1;  
    for(int i = 0;i<k;i++){
      int tmp1 = calc(st,p-1,i);  
      int tmp2;
      tmp2 = calc(nm[st][p-1][i],p-1,jk);
      if(tmp1 != -1){
        if(tmp2 != -1){
          if(mx == -1 || mx > tmp1 + tmp2){
            mx = tmp1 + tmp2;
          };  
        };
      };
    };
    bst[st][p][jk] = mx;
    nm[st][p][jk] = (st/k + (1 << p)) * k + jk;
    return bst[st][p][jk];
  };
};

int main(void){
  int m,o;
  scanf("%d %d %d %d",&k,&n,&m,&o);
  int a,b,t;
  for(int i = 0;i<m;i++){
    scanf("%d %d %d",&a,&b,&t);  
    adj[a][b%k] = t;
  };
  for(int i = 0;i<16;i++){
    for(int j = 0;j<k;j++){
      for(int l = 0;l<n;l++){
        int tmp = calc(l,i,j);  
        //printf("%d %d %d %d %d\n",l,j,i,tmp,nm[l][i][j]);
      };
    };  
  };
  for(int i = 0;i<o;i++){
    scanf("%d %d",&a,&b);
    printf("%d\n",solve(a,b));
  };
  return 0;
};

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:74:13: warning: unused variable 'tmp' [-Wunused-variable]
         int tmp = calc(l,i,j);  
             ^~~
toll.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&k,&n,&m,&o);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&a,&b,&t);  
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
toll.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&a,&b);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 34680 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct
7 Correct 6 ms 1024 KB Output is correct
8 Correct 119 ms 34672 KB Output is correct
9 Correct 112 ms 34552 KB Output is correct
10 Correct 95 ms 33660 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 34664 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 14 ms 1024 KB Output is correct
8 Correct 53 ms 1152 KB Output is correct
9 Correct 108 ms 34552 KB Output is correct
10 Execution timed out 3081 ms 34920 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct
7 Correct 7 ms 1024 KB Output is correct
8 Correct 15 ms 1024 KB Output is correct
9 Correct 10 ms 1024 KB Output is correct
10 Correct 95 ms 34552 KB Output is correct
11 Correct 205 ms 34808 KB Output is correct
12 Correct 318 ms 34680 KB Output is correct
13 Correct 411 ms 34680 KB Output is correct
14 Correct 395 ms 34812 KB Output is correct
15 Correct 1402 ms 21112 KB Output is correct
16 Execution timed out 3071 ms 20984 KB Time limit exceeded

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct
7 Correct 7 ms 1024 KB Output is correct
8 Correct 15 ms 1024 KB Output is correct
9 Correct 10 ms 1024 KB Output is correct
10 Correct 95 ms 34552 KB Output is correct
11 Correct 205 ms 34808 KB Output is correct
12 Correct 318 ms 34680 KB Output is correct
13 Correct 411 ms 34680 KB Output is correct
14 Correct 395 ms 34812 KB Output is correct
15 Correct 1402 ms 21112 KB Output is correct
16 Execution timed out 3071 ms 20984 KB Time limit exceeded

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 34680 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 6 ms 1024 KB Output is correct
7 Correct 6 ms 1024 KB Output is correct
8 Correct 119 ms 34672 KB Output is correct
9 Correct 112 ms 34552 KB Output is correct
10 Correct 95 ms 33660 KB Output is correct
11 Correct 668 ms 34664 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 14 ms 1024 KB Output is correct
18 Correct 53 ms 1152 KB Output is correct
19 Correct 108 ms 34552 KB Output is correct
20 Execution timed out 3081 ms 34920 KB Time limit exceeded
21 Halted 0 ms 0 KB -