oj.uz

Submission #248878

# Submission time Handle Problem Language Result Execution time Memory
248878 2020-07-13T15:54:30 Z ryansee Wombats (IOI13_wombats) C++14
55 / 100
 8958 ms 262148 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[203][203];
	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 41 ms 75384 KB Output is correct
2 Correct 41 ms 75384 KB Output is correct
3 Correct 126 ms 77068 KB Output is correct
4 Correct 42 ms 75384 KB Output is correct
5 Correct 42 ms 75384 KB Output is correct
6 Correct 6 ms 8320 KB Output is correct
7 Correct 6 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 7 ms 9088 KB Output is correct
5 Correct 6 ms 9088 KB Output is correct
6 Correct 6 ms 9088 KB Output is correct
7 Correct 7 ms 9088 KB Output is correct
8 Correct 6 ms 8960 KB Output is correct
9 Correct 7 ms 8960 KB Output is correct
10 Correct 6 ms 9088 KB Output is correct
11 Correct 91 ms 10232 KB Output is correct
12 Correct 7 ms 9088 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1102 ms 24828 KB Output is correct
2 Correct 1087 ms 24828 KB Output is correct
3 Correct 1142 ms 24828 KB Output is correct
4 Correct 1116 ms 25016 KB Output is correct
5 Correct 1095 ms 24892 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 4894 ms 24952 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 44 ms 79352 KB Output is correct
2 Correct 48 ms 79352 KB Output is correct
3 Correct 45 ms 79360 KB Output is correct
4 Correct 85 ms 80124 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1113 ms 24824 KB Output is correct
2 Correct 1099 ms 24696 KB Output is correct
3 Correct 1113 ms 25136 KB Output is correct
4 Correct 1112 ms 24896 KB Output is correct
5 Correct 1074 ms 24952 KB Output is correct
6 Correct 45 ms 79352 KB Output is correct
7 Correct 46 ms 79352 KB Output is correct
8 Correct 47 ms 79480 KB Output is correct
9 Correct 86 ms 80144 KB Output is correct
10 Correct 42 ms 75384 KB Output is correct
11 Correct 41 ms 75384 KB Output is correct
12 Correct 123 ms 77048 KB Output is correct
13 Correct 43 ms 75384 KB Output is correct
14 Correct 42 ms 75384 KB Output is correct
15 Correct 6 ms 8320 KB Output is correct
16 Correct 6 ms 8320 KB Output is correct
17 Correct 6 ms 8320 KB Output is correct
18 Correct 6 ms 9088 KB Output is correct
19 Correct 7 ms 9088 KB Output is correct
20 Correct 7 ms 9088 KB Output is correct
21 Correct 7 ms 9088 KB Output is correct
22 Correct 10 ms 8960 KB Output is correct
23 Correct 7 ms 8960 KB Output is correct
24 Correct 7 ms 9088 KB Output is correct
25 Correct 108 ms 10104 KB Output is correct
26 Correct 7 ms 9088 KB Output is correct
27 Correct 4989 ms 24892 KB Output is correct
28 Runtime error 2385 ms 262148 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 1110 ms 24728 KB Output is correct
2 Correct 1087 ms 24720 KB Output is correct
3 Correct 1132 ms 24952 KB Output is correct
4 Correct 1100 ms 24824 KB Output is correct
5 Correct 1088 ms 24952 KB Output is correct
6 Correct 44 ms 79352 KB Output is correct
7 Correct 44 ms 79360 KB Output is correct
8 Correct 45 ms 79352 KB Output is correct
9 Correct 85 ms 80120 KB Output is correct
10 Correct 41 ms 75384 KB Output is correct
11 Correct 41 ms 75384 KB Output is correct
12 Correct 125 ms 77048 KB Output is correct
13 Correct 41 ms 75384 KB Output is correct
14 Correct 42 ms 75384 KB Output is correct
15 Runtime error 8958 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -