Submission #639538

#TimeUsernameProblemLanguageResultExecution timeMemory
639538NaimSSKarte (COCI18_karte)C++14
120 / 120
107 ms7740 KiB
#include <bits/stdc++.h> //#define int long long #define ld long double #define endl "\n" #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define pb push_back #define mp(a,b) make_pair(a,b) #define ms(v,x) memset(v,x,sizeof(v)) #define all(v) v.begin(),v.end() #define ff first #define ss second #define rep(i, a, b) for(int i = a; i < (b); ++i) #define per(i, a, b) for(int i = b-1; i>=a ; i--) #define trav(a, x) for(auto& a : x) #define allin(a , x) for(auto a : x) #define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end()); #define sz(v) ((int)v.size()) using namespace std; typedef vector<int> vi; #define y1 abacaba //#define left oooooopss #define db(x) cerr << #x <<" == "<<x << endl; #define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl; #define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<ll> vl; std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count()); ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down //inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; } ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));} ll exp(ll b,ll e,ll m){ b%=m; ll ans = 1; for (; e; b = b * b % m, e /= 2) if (e & 1) ans = ans * b % m; return ans; } // debug: void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ cerr << ' ' << H; dbg_out(T...); } #ifdef LOCAL #define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl #else #define dbg(...) 42 #endif // //1 : estados: // posicao do item: i // peso da mochila: P // 2: // Valor de retorno // = valor maximo // 3: Estado base // dp[0][0] = 0 // inf = 1e9 // dp[0][j] = -inf , j!=0 // dp[i][j] = -inf , i!=0 // 4: transicao // dp[i][P] = max(dp[i-1][P-w[i]] + v[i],dp[i-1][P]) //W, which means that the sum of the weights of items taken must be at most W. // res = max(dp[n][w]), 0<=w<=W #define int long long const int N = 103; const int WW = 100100; int w[N],v[N]; int dp[N][WW]; bool vis[N][WW]; // ja calculei dp[i][j] int n,W; const int inf = 1e9; int solve(int pos,int P){ if(pos == 0){ if(P == 0)return 0; return -inf; } if(vis[pos][P])return dp[pos][P]; vis[pos][P] = 1; dp[pos][P] = -inf; dp[pos][P] = max(dp[pos][P],solve(pos-1,P)); if(P-w[pos]>=0){ dp[pos][P] = max(dp[pos][P],solve(pos-1,P - w[pos]) + v[pos]); } return dp[pos][P]; } int32_t main(){ fastio; int n,k; cin >> n >> k; vi a(n); rep(i,0,n)cin >> a[i]; sort(all(a)); reverse(all(a)); reverse(a.begin(),a.begin()+k); int bad=0; rep(i,0,n){ if(bad >= a[i]){ // true }else bad++; } if(bad == k){ per(i,0,n)cout << a[i]<<" \n"[i==0]; }else cout << -1 << endl; // math -> gcd it all // Did u check N=1? Did you switch N,M? }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...