Submission #1069937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069937		8pete8	Wombats (IOI13_wombats)	C++17	55 / 100	20046 ms	26024 KiB

wombats

#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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24