oj.uz

Submission #248907

# Submission time Handle Problem Language Result Execution time Memory
248907 2020-07-13T17:32:25 Z ryansee Wombats (IOI13_wombats) C++14
100 / 100
 7621 ms 193552 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(e-s>=10) l=new node(s,m),r=new node(m+1,e), combine(s,e,l,r);
		else {
			own(s,e);
		}
	}
	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;
		vector<ll> gaps={0,M-1};
		DEC(d,M-1,0){
			vector<ll> ngaps={0};
			assert(M-1-d+2==siz(gaps));
			FOR(i,0,M-1-d){
				ll j=i+d;
				ll opt=-1, best=INF;
				FOR(k,gaps[i],gaps[i+1]){
					ll val=l->dp[i][k]+r->dp[k][j]+C[m][k];
					if(val<best)best=val,opt=k;
				}
				assert(~opt);
				dp[i][j]=best, ngaps.eb(opt);
			}
			gaps=ngaps;
			gaps.eb(M-1);
		}
		gaps={0,M-1};
		DEC(d,M-1,1){
			vector<ll> ngaps={0};
			assert(M-1-d+2==siz(gaps));
			FOR(i,d,M-1){
				ll j=i-d;
				ll opt=-1, best=INF;
				FOR(k,gaps[i-d],gaps[i-d+1]){
					ll val=l->dp[i][k]+r->dp[k][j]+C[m][k];
					if(val<best)best=val,opt=k;
				}
				assert(~opt);
				dp[i][j]=best, ngaps.eb(opt);
			}
			gaps=ngaps;
			gaps.eb(M-1);
		}
	}
	void update(ll s,ll e,int x){
		if(e-s<10){
			own(s,e);
			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);
	}
	void own(ll s,ll 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];
		FOR(r,s+1,e){
			FOR(i,0,M-1)FOR(j,0,M-1)dp[i][j]+=C[r-1][j];
			FOR(i,0,M-1)FOR(j,1,M-1)dp[i][j]=min(dp[i][j],dp[i][j-1]+H[r][j-1]);
			FOR(i,0,M-1)DEC(j,M-2,0)dp[i][j]=min(dp[i][j],dp[i][j+1]+H[r][j]);
		}
	}
}*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 15 ms 18688 KB Output is correct
2 Correct 14 ms 18688 KB Output is correct
3 Correct 94 ms 20216 KB Output is correct
4 Correct 14 ms 18688 KB Output is correct
5 Correct 18 ms 18688 KB Output is correct
6 Correct 8 ms 8320 KB Output is correct
7 Correct 6 ms 8320 KB Output is correct
8 Correct 8 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 8320 KB Output is correct
5 Correct 6 ms 8320 KB Output is correct
6 Correct 7 ms 8320 KB Output is correct
7 Correct 7 ms 8448 KB Output is correct
8 Correct 7 ms 8320 KB Output is correct
9 Correct 7 ms 8320 KB Output is correct
10 Correct 7 ms 8448 KB Output is correct
11 Correct 98 ms 9336 KB Output is correct
12 Correct 7 ms 8448 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 11008 KB Output is correct
2 Correct 147 ms 11008 KB Output is correct
3 Correct 174 ms 11256 KB Output is correct
4 Correct 169 ms 11132 KB Output is correct
5 Correct 167 ms 11008 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 705 ms 11000 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 20 ms 22528 KB Output is correct
2 Correct 17 ms 22528 KB Output is correct
3 Correct 18 ms 22528 KB Output is correct
4 Correct 58 ms 23416 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 11008 KB Output is correct
2 Correct 149 ms 11008 KB Output is correct
3 Correct 173 ms 11008 KB Output is correct
4 Correct 168 ms 11008 KB Output is correct
5 Correct 162 ms 11004 KB Output is correct
6 Correct 17 ms 22528 KB Output is correct
7 Correct 18 ms 22528 KB Output is correct
8 Correct 18 ms 22588 KB Output is correct
9 Correct 59 ms 23416 KB Output is correct
10 Correct 13 ms 18688 KB Output is correct
11 Correct 13 ms 18688 KB Output is correct
12 Correct 95 ms 20216 KB Output is correct
13 Correct 14 ms 18688 KB Output is correct
14 Correct 13 ms 18688 KB Output is correct
15 Correct 6 ms 8352 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 8448 KB Output is correct
19 Correct 6 ms 8448 KB Output is correct
20 Correct 6 ms 8448 KB Output is correct
21 Correct 6 ms 8448 KB Output is correct
22 Correct 6 ms 8320 KB Output is correct
23 Correct 6 ms 8448 KB Output is correct
24 Correct 6 ms 8320 KB Output is correct
25 Correct 87 ms 9340 KB Output is correct
26 Correct 6 ms 8448 KB Output is correct
27 Correct 708 ms 11064 KB Output is correct
28 Correct 2036 ms 100836 KB Output is correct
29 Correct 1973 ms 99576 KB Output is correct
30 Correct 2005 ms 99320 KB Output is correct
31 Correct 2172 ms 101796 KB Output is correct
32 Correct 9 ms 8320 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 11128 KB Output is correct
2 Correct 150 ms 11000 KB Output is correct
3 Correct 173 ms 11008 KB Output is correct
4 Correct 161 ms 11000 KB Output is correct
5 Correct 159 ms 11064 KB Output is correct
6 Correct 19 ms 22560 KB Output is correct
7 Correct 18 ms 22528 KB Output is correct
8 Correct 18 ms 22528 KB Output is correct
9 Correct 58 ms 23336 KB Output is correct
10 Correct 13 ms 18688 KB Output is correct
11 Correct 13 ms 18688 KB Output is correct
12 Correct 96 ms 20216 KB Output is correct
13 Correct 13 ms 18688 KB Output is correct
14 Correct 13 ms 18640 KB Output is correct
15 Correct 2291 ms 182264 KB Output is correct
16 Correct 7621 ms 193552 KB Output is correct
17 Correct 6 ms 8320 KB Output is correct
18 Correct 8 ms 8320 KB Output is correct
19 Correct 7 ms 8320 KB Output is correct
20 Correct 6 ms 8448 KB Output is correct
21 Correct 6 ms 8448 KB Output is correct
22 Correct 7 ms 8448 KB Output is correct
23 Correct 6 ms 8448 KB Output is correct
24 Correct 7 ms 8448 KB Output is correct
25 Correct 7 ms 8448 KB Output is correct
26 Correct 7 ms 8448 KB Output is correct
27 Correct 88 ms 10744 KB Output is correct
28 Correct 6 ms 8448 KB Output is correct
29 Correct 683 ms 11112 KB Output is correct
30 Correct 2028 ms 104568 KB Output is correct
31 Correct 7139 ms 190644 KB Output is correct
32 Correct 7220 ms 190612 KB Output is correct
33 Correct 1960 ms 103012 KB Output is correct
34 Correct 7033 ms 188768 KB Output is correct
35 Correct 2005 ms 103020 KB Output is correct
36 Correct 7002 ms 188972 KB Output is correct
37 Correct 2197 ms 106304 KB Output is correct
38 Correct 7283 ms 191156 KB Output is correct
39 Correct 6 ms 8320 KB Output is correct
40 Correct 7078 ms 189008 KB Output is correct