oj.uz

Submission #1069937

# Submission time Handle Problem Language Result Execution time Memory
1069937 2024-08-22T10:18:56 Z 8pete8 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 26024 KB 
#include "wombats.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
const int inf=1e9;
int dist[202][202],costv[5005][202],costh[5005][200];
int n,m;
int pref[202];
void cal(){
    for(int st=0;st<m;st++)for(int go=0;go<m;go++){
        if(st!=go)dist[st][go]=inf;
        else dist[st][go]=0;
    }
    for(int r=0;r<n;r++)for(int st=0;st<m;st++){
        int mncost=inf,add=0;
        for(int go=0;go<m;go++){
            mncost=min(mncost,dist[st][go]-add);
            pref[go]=mncost+add;
            add+=costh[r][go];
        }
        mncost=inf,add=0;
        for(int go=m-1;go>=0;go--){
            mncost=min(mncost,dist[st][go]-add);
            dist[st][go]=min(pref[go],mncost+add);
            if(r!=n-1)dist[st][go]+=costv[r][go];
            if(go)add+=costh[r][go-1];
        }
    }
}
void init(int R, int C, int H[5000][200], int V[5000][200]){
    n=R,m=C;
    for(int i=0;i<n;i++)for(int j=0;j<m-1;j++)costh[i][j]=H[i][j];
    for(int i=0;i<n-1;i++)for(int j=0;j<m;j++)costv[i][j]=V[i][j];
    cal();
}
void changeH(int P, int Q, int W){
    costh[P][Q]=W;
    cal();
}
void changeV(int P, int Q, int W) {
    costv[P][Q]=W;
    cal();
}
int escape(int V1, int V2){
    return dist[V1][V2];
}

/*
we can compute [start][at][row] 
=200x200x5000
for each update
how to improve?
*/

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;
      |      ^~~
wombats.cpp:33:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   33 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
wombats.cpp:38:10: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | void cal(){
      |          ^
wombats.cpp:59:59: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   59 | void init(int R, int C, int H[5000][200], int V[5000][200]){
      |                                                           ^
wombats.cpp:65:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   65 | void changeH(int P, int Q, int W){
      |                                 ^
wombats.cpp:69:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   69 | void changeV(int P, int Q, int W) {
      |                                 ^
wombats.cpp:73:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 | int escape(int V1, int V2){
      |                          ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 11868 KB Output is correct
2 Correct 14 ms 12072 KB Output is correct
3 Correct 51 ms 14720 KB Output is correct
4 Correct 16 ms 11864 KB Output is correct
5 Correct 14 ms 11864 KB Output is correct
6 Correct 1 ms 4540 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6616 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6596 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 40 ms 8980 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 6812 KB Output is correct
2 Correct 185 ms 6748 KB Output is correct
3 Correct 184 ms 6748 KB Output is correct
4 Correct 196 ms 6744 KB Output is correct
5 Correct 180 ms 6812 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 922 ms 6832 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15964 KB Output is correct
2 Correct 38 ms 15964 KB Output is correct
3 Correct 35 ms 15964 KB Output is correct
4 Correct 52 ms 17496 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 6744 KB Output is correct
2 Correct 196 ms 6996 KB Output is correct
3 Correct 183 ms 6744 KB Output is correct
4 Correct 183 ms 6816 KB Output is correct
5 Correct 194 ms 6996 KB Output is correct
6 Correct 35 ms 15964 KB Output is correct
7 Correct 33 ms 16180 KB Output is correct
8 Correct 35 ms 15960 KB Output is correct
9 Correct 51 ms 17480 KB Output is correct
10 Correct 14 ms 11864 KB Output is correct
11 Correct 15 ms 11868 KB Output is correct
12 Correct 53 ms 14676 KB Output is correct
13 Correct 15 ms 11868 KB Output is correct
14 Correct 14 ms 11864 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 0 ms 4444 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6488 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6488 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 43 ms 8788 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct
27 Correct 938 ms 6832 KB Output is correct
28 Execution timed out 20042 ms 19800 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 6744 KB Output is correct
2 Correct 185 ms 6800 KB Output is correct
3 Correct 183 ms 6744 KB Output is correct
4 Correct 183 ms 6744 KB Output is correct
5 Correct 184 ms 6996 KB Output is correct
6 Correct 34 ms 16216 KB Output is correct
7 Correct 34 ms 15964 KB Output is correct
8 Correct 34 ms 15964 KB Output is correct
9 Correct 51 ms 17372 KB Output is correct
10 Correct 14 ms 11868 KB Output is correct
11 Correct 14 ms 12068 KB Output is correct
12 Correct 51 ms 14616 KB Output is correct
13 Correct 14 ms 11868 KB Output is correct
14 Correct 14 ms 11920 KB Output is correct
15 Correct 1937 ms 26024 KB Output is correct
16 Execution timed out 20046 ms 24148 KB Time limit exceeded
17 Halted 0 ms 0 KB -