oj.uz

Submission #248879

# Submission time Handle Problem Language Result Execution time Memory
248879 2020-07-13T16:08:09 Z ryansee Wombats (IOI13_wombats) C++14
55 / 100
 4937 ms 262144 KB 
#include "wombats.h"

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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=int; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

// #define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (300006)
ll n, M, H[5003][203], C[5003][203];
struct node {
	ll dp[103][103];
	node*l,*r;
	node(int s,int e){
		int m=(s+e)>>1;
		if(s^e) l=new node(s,m),r=new node(m+1,e), combine(s,e,l,r);
		else {
			FOR(i,0,M-1) FOR(j,i,M-1) if(i^j) dp[i][j]=dp[i][j-1]+H[s][j-1]; else dp[i][j]=0;
			FOR(i,0,M-1) FOR(j,0,i-1) dp[i][j]=dp[j][i];
		}
	}
	void combine(ll s,ll e,node* l, node* r){
		ll m=(s+e)>>1;
		FOR(i,0,M-1)FOR(j,0,M-1){
			dp[i][j]=INF;
			FOR(k,0,M-1) dp[i][j]=min(dp[i][j],l->dp[i][k]+r->dp[k][j]+C[m][k]);
		}
	}
	void update(ll s,ll e,int x){
		if(s==e){
			FOR(i,0,M-1) FOR(j,i,M-1) if(i^j) dp[i][j]=dp[i][j-1]+H[s][j-1]; else dp[i][j]=0;
			FOR(i,0,M-1) FOR(j,0,i-1) dp[i][j]=dp[j][i];
			return;
		}
		ll m=(s+e)>>1;
		if(x>m)r->update(m+1,e,x);else l->update(s,m,x);
		combine(s,e,l,r);
	}
}*seg;
void init(int _r, int _c, int HH[5000][200], int VV[5000][200]) {
    /* ... */
    n=_r, M=_c;
    FOR(i,0,4999)FOR(j,0,199)H[i][j]=HH[i][j],C[i][j]=VV[i][j];
    seg=new node(0, n-1);
}

void changeH(int P, int Q, int W) {
    /* ... */
    H[P][Q]=W;
    seg->update(0,n-1,P);
}

void changeV(int P, int Q, int W) {
    /* ... */
    C[P][Q]=W;
    seg->update(0,n-1,P+1);
}

int escape(int V1, int V2) {
    return seg->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]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 53368 KB Output is correct
2 Correct 31 ms 53248 KB Output is correct
3 Correct 109 ms 54964 KB Output is correct
4 Correct 27 ms 53248 KB Output is correct
5 Correct 27 ms 53248 KB Output is correct
6 Correct 6 ms 8320 KB Output is correct
7 Correct 5 ms 8320 KB Output is correct
8 Correct 5 ms 8320 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8320 KB Output is correct
2 Correct 6 ms 8320 KB Output is correct
3 Correct 6 ms 8320 KB Output is correct
4 Correct 6 ms 8832 KB Output is correct
5 Correct 6 ms 8832 KB Output is correct
6 Correct 6 ms 8832 KB Output is correct
7 Correct 6 ms 8832 KB Output is correct
8 Correct 7 ms 8704 KB Output is correct
9 Correct 6 ms 8704 KB Output is correct
10 Correct 6 ms 8704 KB Output is correct
11 Correct 90 ms 9848 KB Output is correct
12 Correct 7 ms 8832 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1092 ms 16908 KB Output is correct
2 Correct 1069 ms 16764 KB Output is correct
3 Correct 1097 ms 16760 KB Output is correct
4 Correct 1102 ms 16796 KB Output is correct
5 Correct 1083 ms 16764 KB Output is correct
6 Correct 6 ms 8320 KB Output is correct
7 Correct 6 ms 8320 KB Output is correct
8 Correct 6 ms 8320 KB Output is correct
9 Correct 4912 ms 16888 KB Output is correct
10 Correct 6 ms 8320 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 61312 KB Output is correct
2 Correct 32 ms 61304 KB Output is correct
3 Correct 32 ms 61304 KB Output is correct
4 Correct 74 ms 62072 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1107 ms 16760 KB Output is correct
2 Correct 1071 ms 16760 KB Output is correct
3 Correct 1103 ms 16768 KB Output is correct
4 Correct 1117 ms 16760 KB Output is correct
5 Correct 1076 ms 16888 KB Output is correct
6 Correct 32 ms 61304 KB Output is correct
7 Correct 31 ms 61304 KB Output is correct
8 Correct 32 ms 61304 KB Output is correct
9 Correct 75 ms 62072 KB Output is correct
10 Correct 27 ms 53240 KB Output is correct
11 Correct 27 ms 53248 KB Output is correct
12 Correct 110 ms 54904 KB Output is correct
13 Correct 29 ms 53248 KB Output is correct
14 Correct 27 ms 53248 KB Output is correct
15 Correct 6 ms 8320 KB Output is correct
16 Correct 7 ms 8320 KB Output is correct
17 Correct 5 ms 8320 KB Output is correct
18 Correct 7 ms 8832 KB Output is correct
19 Correct 7 ms 8832 KB Output is correct
20 Correct 6 ms 8832 KB Output is correct
21 Correct 6 ms 8832 KB Output is correct
22 Correct 6 ms 8704 KB Output is correct
23 Correct 7 ms 8704 KB Output is correct
24 Correct 6 ms 8832 KB Output is correct
25 Correct 90 ms 9848 KB Output is correct
26 Correct 7 ms 8832 KB Output is correct
27 Correct 4937 ms 16804 KB Output is correct
28 Runtime error 4501 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1095 ms 16760 KB Output is correct
2 Correct 1087 ms 16684 KB Output is correct
3 Correct 1120 ms 16888 KB Output is correct
4 Correct 1104 ms 16888 KB Output is correct
5 Correct 1082 ms 16888 KB Output is correct
6 Correct 33 ms 61312 KB Output is correct
7 Correct 32 ms 61304 KB Output is correct
8 Correct 34 ms 61312 KB Output is correct
9 Correct 72 ms 62072 KB Output is correct
10 Correct 27 ms 53240 KB Output is correct
11 Correct 27 ms 53284 KB Output is correct
12 Correct 110 ms 54904 KB Output is correct
13 Correct 28 ms 53240 KB Output is correct
14 Correct 26 ms 53248 KB Output is correct
15 Runtime error 320 ms 42748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -