oj.uz

답안 #1012546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1012546 2024-07-02T10:20:28 Z amirhoseinfar1385 웜뱃 (IOI13_wombats) C++17
55 / 100
 20000 ms 34540 KB 
#include "wombats.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
const long long maxn=5000+10,maxm=200+10;
long long allr[maxn][maxm],allc[maxn][maxm],dp[maxn][maxm],n,m,ps[maxm],suf[maxm],inf=1e11+5,psmx[maxn],sufmx[maxn];

void calc(){
    for(long long k=1;k<=m;k++){
        for(long long j=1;j<=m;j++){
            ps[j]=ps[j-1]+allr[n][j-1];
        }
        for(long long j=m;j>=1;j--){
            suf[j]=suf[j+1]+allr[n][j];
        }
        for(int j=1;j<=m;j++){
            if(j<=k){
                dp[j][k]=ps[k]-ps[j];
            }else{
                dp[j][k]=suf[k]-suf[j];
            }
        }
    //    for(long long j=1;j<=m;j++){
      //      cout<<dp[j][k]<<" ";
     //   }
       // cout<<endl;
        psmx[0]=sufmx[m+1]=inf;
        for(long long i=n-1;i>=1;i--){
            for(long long j=1;j<=m;j++){
                ps[j]=ps[j-1]+allr[i][j-1];
            }
            for(long long j=m;j>=1;j--){
                suf[j]=suf[j+1]+allr[i][j];
            }
            for(long long j=1;j<=m;j++){
                psmx[j]=min(psmx[j-1],suf[j]+dp[j][k]+allc[i][j]);
            }
            for(long long j=m;j>=1;j--){
                sufmx[j]=min(sufmx[j+1],ps[j]+dp[j][k]+allc[i][j]);
            }
            for(long long j=1;j<=m;j++){
            //    cout<<psmx[j-1]<<" "<<suf[j]<<" "<<sufmx[j+1]<<" "<<ps[j]<<endl;
                dp[j][k]=min(dp[j][k]+allc[i][j],min(psmx[j-1]-suf[j],sufmx[j+1]-ps[j]));
            }
        //    cout<<"salam"<<endl;
          //  for(long long j=1;j<=m;j++){
            //    cout<<dp[j][k]<<" ";
        //    }
          //  cout<<endl;
        }
    }
}

void init(int R,int C,int H[5000][200],int V[5000][200]) {
    n=R;
    m=C;
    for(long long i=1;i<=n;i++){
        for(long long j=1;j<=m-1;j++){
            allr[i][j]=H[i-1][j-1];
        }
    }
    for(long long i=1;i<=n-1;i++){
        for(long long j=1;j<=m;j++){
            allc[i][j]=V[i-1][j-1];          
        }
    }
    calc();
}

void changeH(int P,int Q,int W) {
    P++;
    Q++;
    allr[P][Q]=W;
    calc();
}

void changeV(int P,int Q,int W) {
    P++;
    Q++;
    allc[P][Q]=W;
    calc();
}

int escape(int V1,int V2) {
    V1++;
    V2++;
    return dp[V1][V2];    
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 16988 KB Output is correct
2 Correct 19 ms 16984 KB Output is correct
3 Correct 54 ms 19280 KB Output is correct
4 Correct 27 ms 16988 KB Output is correct
5 Correct 16 ms 16984 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8636 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 40 ms 10440 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 453 ms 8796 KB Output is correct
2 Correct 409 ms 8536 KB Output is correct
3 Correct 437 ms 8792 KB Output is correct
4 Correct 423 ms 8796 KB Output is correct
5 Correct 453 ms 8796 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2130 ms 8796 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 26936 KB Output is correct
2 Correct 105 ms 26716 KB Output is correct
3 Correct 106 ms 26716 KB Output is correct
4 Correct 127 ms 27984 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 436 ms 8792 KB Output is correct
2 Correct 420 ms 8772 KB Output is correct
3 Correct 434 ms 8792 KB Output is correct
4 Correct 460 ms 8796 KB Output is correct
5 Correct 409 ms 8796 KB Output is correct
6 Correct 108 ms 26712 KB Output is correct
7 Correct 97 ms 26916 KB Output is correct
8 Correct 107 ms 26712 KB Output is correct
9 Correct 120 ms 27988 KB Output is correct
10 Correct 18 ms 16988 KB Output is correct
11 Correct 18 ms 17036 KB Output is correct
12 Correct 60 ms 19180 KB Output is correct
13 Correct 19 ms 16988 KB Output is correct
14 Correct 19 ms 16988 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8796 KB Output is correct
20 Correct 1 ms 8536 KB Output is correct
21 Correct 1 ms 8536 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8536 KB Output is correct
24 Correct 1 ms 8540 KB Output is correct
25 Correct 38 ms 10468 KB Output is correct
26 Correct 1 ms 8536 KB Output is correct
27 Correct 2105 ms 8708 KB Output is correct
28 Execution timed out 20028 ms 28752 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 460 ms 8796 KB Output is correct
2 Correct 442 ms 8540 KB Output is correct
3 Correct 447 ms 8796 KB Output is correct
4 Correct 444 ms 8792 KB Output is correct
5 Correct 417 ms 8792 KB Output is correct
6 Correct 97 ms 26716 KB Output is correct
7 Correct 106 ms 26964 KB Output is correct
8 Correct 102 ms 26716 KB Output is correct
9 Correct 121 ms 28240 KB Output is correct
10 Correct 19 ms 16984 KB Output is correct
11 Correct 19 ms 16984 KB Output is correct
12 Correct 55 ms 19796 KB Output is correct
13 Correct 18 ms 16988 KB Output is correct
14 Correct 17 ms 16984 KB Output is correct
15 Correct 4418 ms 34540 KB Output is correct
16 Execution timed out 20044 ms 31196 KB Time limit exceeded
17 Halted 0 ms 0 KB -