Submission #100802

#TimeUsernameProblemLanguageResultExecution timeMemory
100802ScayreK blocks (IZhO14_blocks)C++14
53 / 100
1071 ms512 KiB
/////////////////////////// // INFO // // // // Handle -> Scayre // // // // Template vers. 1.1 // // // // It'll be accepted // // // /////////////////////////// //████╗████████╗██╗███████╗══███╗═══███╗████████╗════// //═██╔╝═══██╔══╝╚█║██╔════╝══████╗═████║██╔═════╝═══// //═██║════██║════╚╝███████╗══██╔████╔██║█████╗══════// //═██║════██║══════╚════██║══██║╚██╔╝██║██╔══╝══════// //████╗═══██║══════███████║══██║═╚═╝═██║███████╗═════// #include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <string> #include <bitset> #include <cstdio> #include <limits> #include <complex> #include <vector> #include <climits> #include <cstring> #include <cstdlib> #include <fstream> #include <numeric> #include <sstream> #include <cassert> #include <iomanip> #include <iostream> #include <algorithm> #define ll long long #define ld long double #define ull unsigned ll #define ioi exit(0); #define f first #define s second #define inf (int)1e9 + 7 #define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0); #define mp(x,y) make_pair(x,y) #define lb(x) lower_bound(x) #define ub(x) upper_bound(x) #define pb push_back #define ppb pop_back #define bitcoin __builtin_popcount #define endl "\n" #define in(x) insert(x) #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() #define pw2(x) (1<<x) //2^x #define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it) #define sqr(x) ((x) * 1ll * (x)) #define UpdateRandom srand (time(NULL)); using namespace std; const int N = (int)2e5 + 7, MOD = (int)1e9 + 7; int n,k; int a[N]; bool was[N][102]; ll dp[N][102]; ll calc(int x,int y=0){ int mx=0; if(y==k-1){ for(int i=x;i<=n;i++){ mx=max(mx,a[i]); } return mx; } if(was[x][y])return dp[x][y]; was[x][y]=1; dp[x][y]=inf; //cout << n-k+y << endl; for(int i=x;i<=((n-k+1)+y);i++){ mx=max(mx,a[i]); dp[x][y]=min(dp[x][y],calc(i+1,y+1)+mx); } return dp[x][y]; } int main(){ #ifdef IOI2019 freopen ("in.txt", "r", stdin); #endif cin >> n >> k; for(int i=1;i<=n;i++){ cin >> a[i]; } cout << calc(1) << endl; #ifdef IOI2019 cout << "\nTime Elapsed : " << clock () * 1.0 / CLOCKS_PER_SEC << endl; #endif ioi }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...