oj.uz

답안 #470816

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
470816 2021-09-05T20:20:07 Z robell 건포도 (IOI09_raisins) C++14
100 / 100
 1473 ms 49264 KB 
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
#define pb push_back
#define eb emplace_back
#define countbits __builtin_popcount
#define beg0 __builtin_clz
#define terminal0 __builtin_ctz
#define mod 1e9+7
void setIO(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
void setIO(string f){
	freopen((f+".in").c_str(),"r",stdin);
	freopen((f+".out").c_str(),"w",stdout);
	setIO();
}
int N, M;
ll dp[50][50][50][50];
int g[50][50];
int p[50][50];
ll findSum(pair<int,int> b, pair<int,int> t){
	ll sum = p[t.first][t.second];
	if (b.second) sum-=p[t.first][b.second-1];
	if (b.first) sum-=p[b.first-1][t.second];
	if (b.second&&b.first) sum+=p[b.first-1][b.second-1];
	return sum;
}
ll checkStruct(pair<int,int> b, pair<int,int> t){
	if (dp[b.first][b.second][t.first][t.second]!=1e18){
		return dp[b.first][b.second][t.first][t.second];
	}
	ll totmin = 1e18;
	for (int i=b.first;i<t.first;i++){
		totmin=min(totmin,checkStruct({b.first,b.second},{i,t.second})+checkStruct({i+1,b.second},{t.first,t.second}));
	}
	for (int i=b.second;i<t.second;i++){
		totmin=min(totmin,checkStruct({b.first,b.second},{t.first,i})+checkStruct({b.first,i+1},{t.first,t.second}));
	}
	if (totmin==1e18){
		dp[b.first][b.second][t.first][t.second]=0;
		return 0;
	}else{
		dp[b.first][b.second][t.first][t.second]=findSum(b,t)+totmin;
		return findSum(b,t)+totmin;
	}
}
int main(){
	setIO();
	cin >> N >> M;
	for (int i=0;i<N;i++){
		for (int j=0;j<M;j++){
			cin >> g[i][j];
		}
	}
	for (int i=0;i<N;i++){
		for (int j=0;j<M;j++){
			p[i][j]=g[i][j];
			if (i) p[i][j]+=p[i-1][j];
			if (j) p[i][j]+=p[i][j-1];
			if (i&&j) p[i][j]-=p[i-1][j-1];
		}
	}
	for (int i=0;i<N;i++){
		for (int j=0;j<M;j++){
			for (int a=0;a<N;a++){
				for (int b=0;b<M;b++){
					dp[i][j][a][b]=1e18;
				}
			}
		}
	}
	cout << checkStruct({0,0},{N-1,M-1}) << "\n";
}

Compilation message

raisins.cpp: In function 'void setIO(std::string)':
raisins.cpp:19:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  freopen((f+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
raisins.cpp:20:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  freopen((f+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 2 ms 1484 KB Output is correct
8 Correct 18 ms 4832 KB Output is correct
9 Correct 36 ms 7244 KB Output is correct
10 Correct 47 ms 8848 KB Output is correct
11 Correct 39 ms 7116 KB Output is correct
12 Correct 145 ms 16600 KB Output is correct
13 Correct 245 ms 21876 KB Output is correct
14 Correct 65 ms 8908 KB Output is correct
15 Correct 301 ms 24784 KB Output is correct
16 Correct 26 ms 8396 KB Output is correct
17 Correct 124 ms 17676 KB Output is correct
18 Correct 766 ms 38116 KB Output is correct
19 Correct 1260 ms 46580 KB Output is correct
20 Correct 1473 ms 49264 KB Output is correct