Submission #1207575

#TimeUsernameProblemLanguageResultExecution timeMemory
1207575mychecksedadCoin Collecting (JOI19_ho_t4)C++17
8 / 100
9 ms12512 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1500+100, M = 1e5+10, K = 52, MX = 30; const ll INF = 1e18; int n; ll dp[N][N]; array<ll, 2> a[N]; void solve(){ cin >> n; ll ans = 0; vector<array<int, 2>> pt(n + 1); for(int i = 1; i <= 2*n; ++i){ cin >> a[i][0] >> a[i][1]; if(a[i][0] < 1){ ans += 1 - a[i][0]; a[i][0] = 1; } if(a[i][0] > n){ ans += a[i][0] - n; a[i][0] = n; } if(a[i][1] < 1){ ans += 1 - a[i][1]; a[i][1] = 1; } if(a[i][1] > 2){ ans += a[i][1] - 2; a[i][1] = 2; } pt[a[i][0]][a[i][1] - 1]++; // cerr << a[i][0] << ' ' << a[i][1] << '\n'; } for(int i = 0; i <= n; ++i){ for(int j = 0; j <= n + 1; ++j) dp[i][j] = INF; } dp[0][0] = 0; int cnt = 0; for(int i = 1; i <= n; ++i){ for(int j = 0; j <= n; ++j) dp[i][j] = dp[i - 1][j]; int x = pt[i][1]; int y = pt[i][0]; for(int k = 1; k <= x + y; ++k){ ++cnt; for(int j = n; j >= 0; --j){ int cost1 = (k <= x ? 1 : 0) + abs(i - (cnt - j)); // moving to down int cost2 = (k > x ? 1 : 0) + abs(i - j); // moving to down if(j > 0) dp[i][j] = min(dp[i][j] + cost1, dp[i][j - 1] + cost2); else dp[i][j] = dp[i][j] + cost1; } } for(int j = 0; j < cnt/2 - 5;++j) dp[i][j] = INF; for(int j = cnt/2 + 6; j <= n;++j) dp[i][j] = INF; // for(int j = 0; j <= n; ++j){ // cerr << i << ' ' << j << ' ' << dp[i][j] << '\n'; // } // en; } cout << ans + dp[n][n]; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...