Submission #224090

#	Time	Username	Problem	Language	Result	Execution time	Memory
224090		SomeoneUnknown	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	193 ms	63992 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, l;
    scanf("%d %d", &n, &l);
    int dsts[n];
    int ts[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &dsts[i]);
    }
    for(int i = 0; i < n; i++){
        scanf("%d", &ts[i]);
    }
    int sttes[n+1][n+1][n+1][2]; //cstationsV, ccstationsV, stamps, pos
    int lmit = 1000000009;
    //for(int i = 0; i <= n; i++)
    //    for(int j = 0; j <= n; j++) sttes[i][j][0] = lmit;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            for(int k = 0; k <= n; k++)
                sttes[i][j][k][0] = sttes[i][j][k][1] = lmit;
    sttes[0][0][0][0] = sttes[0][0][0][1] = 0;
    int best = 0;
    for(int i = 0; i < n; i++){ //stamp count
        for(int j = 0; j <= n; j++){ //clockwise distance
            for(int k = 0; k <= n; k++){ //counterclockwise distance
                if(j + k >= n) continue;
                int ccd, cccd, ncd, nccd;
                ccd = cccd = 0;
                if(j != 0) ccd = dsts[j-1];
                if(k != 0) cccd = l-dsts[n-k];
                ncd = dsts[j];
                nccd = l-dsts[n-k-1];
                //printf("%d %d %d %d %d %d %d\n", i, j, k, ccd, cccd, ncd, nccd);
                int ctspnt = sttes[i][j][k][0];
                int cctspnt = sttes[i][j][k][1];
                sttes[i+(ncd-ccd+ctspnt <= ts[j])][j+1][k][0] = min(sttes[i+(ncd-ccd+ctspnt <= ts[j])][j+1][k][0], ctspnt+ncd-ccd);
                if(sttes[i+1][j+1][k][0] < lmit){
                    best = i+1;
                    //printf("%d %d %d %d %d %d\n", i+1, j+1, k, 0, sttes[i+1][j+1][k][0], sttes[i][j][k][0]);
                }
                sttes[i+(nccd+ccd+ctspnt <= ts[n-k-1])][j][k+1][1] = min(sttes[i+(nccd+ccd+ctspnt <= ts[n-k-1])][j][k+1][1], nccd+ccd+ctspnt);
                if(sttes[i+1][j][k+1][1] < lmit){
                    best = i+1;
                    //printf("%d %d %d %d %d\n", i+1, j, k+1, 1, sttes[i+1][j][k+1][1]);
                }
                sttes[i+(nccd-cccd+cctspnt <= ts[n-k-1])][j][k+1][1] = min(sttes[i+(nccd-cccd+cctspnt <= ts[n-k-1])][j][k+1][1], nccd-cccd+cctspnt);
                if(sttes[i+1][j][k+1][1] < lmit){
                    best = i+1;
                    //printf("%d %d %d %d %d\n", i+1, j, k+1, 1, sttes[i+1][j][k+1][1]);
                }
                sttes[i+(ncd+cccd+cctspnt <= ts[j])][j+1][k][0] = min(sttes[i+(ncd+cccd+cctspnt <= ts[j])][j+1][k][0], ncd+cccd+cctspnt);
                if(sttes[i+1][j+1][k][0] < lmit){
                    best = i+1;
                    //printf("%d %d %d %d %d\n", i+1, j+1, k, 0, sttes[i+1][j+1][k][0]);
                }
            }
        }
    }
    /*for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int k = 0; k <= n; k++){
                printf("(%d,%d) ", sttes[i][j][k][0], sttes[i][j][k][0]);
            }
            printf("\n");
        }
        printf("\n");
    }//*/
    printf("%d", best);
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:6: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:10:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &dsts[i]);
         ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ts[i]);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75