제출 #936170

#제출 시각아이디문제언어결과실행 시간메모리
936170shoryu386The short shank; Redemption (BOI21_prison)C++17
15 / 100
2028 ms251984 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int n, d, t; #define MAX 4007 int arr[MAX], dp[MAX][MAX]; int memo[MAX][MAX]; void costPrecomp(int l){; int ans = 0; if (arr[l] <= t) memo[l][l] = 1, ans = 1; else memo[l][l] = 0, ans = 0; int carry = arr[l] + 1; for (int x = l+1; x < n; x++){ int val = min(arr[x], carry); if (val <= t) ans++; carry = min(carry, arr[x]); carry += 1; memo[l][x] = ans; } } inline int cost(int l, int r){ return memo[l][r];} main(){ cin >> n >> d >> t; for (int x = 0; x < n; x++) cin >> arr[x]; for (int x = 0; x < n; x++) costPrecomp(x); memset(dp, 63, sizeof(dp)); for (int x = 0; x < n; x++){ dp[x][1] = min(dp[x][1], cost(0, x)); vector<int> test; for (int z = 1; z <= n; z++){ int bestLoc = -1; for (int y = 0; y < x; y++){ if (dp[y][z-1] + cost(y+1, x) < dp[x][z]) dp[x][z] = dp[y][z-1] + cost(y+1, x), bestLoc = y; } if (bestLoc != -1) test.push_back(bestLoc); } //for (auto z : test) cout << z << ' '; //cout << '\n'; vector<int> check = test; sort(check.begin(), check.end()); assert(check == test); } cout << dp[n-1][d+1]; }

컴파일 시 표준 에러 (stderr) 메시지

prison.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...