oj.uz

Submission #224204

# Submission time Handle Problem Language Result Execution time Memory
224204 2020-04-17T12:44:37 Z dantoh000 Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 69 ms 135288 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
const ll INF = 1000000000000000000;
int n,l;
int p[205], t[205];
ll mem[2][205][205][205];
///min time to reach state:
///[0,x[i]] U [x[j],L] visited;
///at x[i]/ x[j] depends on d
///k stamps collect;
ll dp(int d, int i, int j, int k){
    if (mem[d][i][j][k] != -1) return mem[d][i][j][k];
    ll res = INF;
    ///try not taking anything
    if (d == 0 && i != 0){
        res = min(dp(0,i-1,j,k)+p[i]-p[i-1],
                  dp(1,i-1,j,k)+l-p[j]+p[i-1]);
    }
    if (d == 1 && j != n+1){
        res = min(dp(0,i,j+1,k)+l-p[j]+p[i],
                  dp(1,i,j+1,k)+p[j+1]-p[j]);
    }
    if (k){
        ll T = INF;
        if (d == 0 && i != 0){
            T = dp(0,i-1,j,k-1)+p[i]-p[i-1];
            //printf("if from %d to %d clock, take %lld+%d\n",i-1,i,dp(0,i-1,j,k-1),p[i]-p[i-1]);
            if (T <= t[i]) res = min(res,T);
            T = dp(1,i-1,j,k-1)+l-p[j]+p[i];
            //printf("if from %d to %d clock, take %lld+%d\n",j,i,dp(1,i-1,j,k-1),l-p[j]+p[i]);
            if (T <= t[i]) res = min(res,T);
        }
        if (d == 1 && j != n+1){
            T = dp(0,i,j+1,k-1)+l-p[j]+p[i];
            //printf("if from %d to %d anticlock, take %lld+%d\n",i,j,dp(0,i,j+1,k-1),l-p[j]+p[i]);
            if (T <= t[j]) res = min(res,T);
            T = dp(1,i,j+1,k-1)+p[j+1]-p[j];
            //printf("if from %d to %d anticlock, take %lld+%d\n",j+1,j,dp(1,i,j+1,k-1),p[j+1]-p[j]);
            if (T <= t[j]) res = min(res,T);
        }
    }
    //printf("%d %d %d %d %lld\n",d,i,j,k,res);
    return mem[d][i][j][k] = res;
}
int main(){
    scanf("%d%d",&n,&l);
    for (int i = 1; i <= n; i++){
        scanf("%d",&p[i]);
    }
    p[n+1] = l;
    for (int i = 1; i <= n; i++){
        scanf("%d",&t[i]);
    }
    t[0] = t[n+1] = 0;
    memset(mem,-1,sizeof(mem));
    mem[0][0][n+1][0] = mem[1][0][n+1][0] = 0;
    int ans = 0;
    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= n; j++){
            if (dp(0,i,i+1,j) < INF || dp(1,i,i+1,j) < INF) {
                //printf("%d %d %d\n",i,i+1,j);
                ans = max(ans,j);
            }
        }
    }
    printf("%d ",ans);



}

Compilation message

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&l);
     ~~~~~^~~~~~~~~~~~~~
ho_t3.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
         ~~~~~^~~~~~~~~~~~
ho_t3.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&t[i]);
         ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 135288 KB Output is correct
2 Correct 69 ms 135032 KB Output is correct
3 Incorrect 66 ms 135180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 135288 KB Output is correct
2 Correct 69 ms 135032 KB Output is correct
3 Incorrect 66 ms 135180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 135288 KB Output is correct
2 Correct 69 ms 135032 KB Output is correct
3 Incorrect 66 ms 135180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 135288 KB Output is correct
2 Correct 69 ms 135032 KB Output is correct
3 Incorrect 66 ms 135180 KB Output isn't correct
4 Halted 0 ms 0 KB -