제출 #1045507

#제출 시각아이디문제언어결과실행 시간메모리
1045507RequiemSails (IOI07_sails)C++17
25 / 100
1071 ms6492 KiB
#include<bits/stdc++.h> #define int long long #define pb push_back #define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #define MOD 1000000007 #define inf 1e18 #define fi first #define se second #define endl "\n" #define FOR(i,a,b) for(int i=a;i<=b;i++) #define FORD(i,a,b) for(int i=a;i>=b;i--) #define sz(a) ((int)(a).size()) #define pi 3.14159265359 #define TASKNAME "sails" template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; } template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; } using namespace std; typedef pair<int,int> ii; typedef pair<int,ii> iii; typedef vector<int> vi; const int MAXN = 1e5 + 9; struct Poles{ //cây cột chứa các sail int height, numSail; } P[MAXN]; int n; void input(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> P[i].height >> P[i].numSail; } } namespace subtask1{ bool check(){ return n <= 200; } vector<int> state[MAXN]; int ans = inf; map<int, int> cnt; int calc(){ cnt.clear(); int sum = 0; for(int i = n; i >= 1; i--){ for(auto x: state[i]){ sum += cnt[x]; cnt[x]++; } } return sum; } void backtrack(int pos, int numChosen, int last){ if (pos == n + 1){ minimize(ans, calc()); return; } if (numChosen < P[pos].numSail){ for(int j = last + 1; j <= P[pos].height; j++){ state[pos].pb(j); backtrack(pos, numChosen + 1, j); state[pos].pop_back(); } } else{ backtrack(pos + 1, 0, 0); } } void solve(){ backtrack(1, 0, 0); cout << ans << endl; } } /** * IOI 2007 Sail Solution: * bài này mình đang suy nghĩ đến việc tham lam. * Với 1 thằng, ta sẽ cố chọn những thằng cao nhất có thể chưa được chọn vì nó là tốt nhất * Xét đến vị trí i, liệu kết quả của ta có xuất phát từ vị trí i + 1 hay không. * * Ưu tiên số 1: Rải đều ra. * ƯU tiên số 2: chọn càng cao càng tốt. * * */ namespace subtask2{ bool check(){ return true; } int cnt[MAXN]; ii temp[MAXN]; bool custom_cmp(ii a, ii b){ return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi); } void solve(){ int ans1 = 0; memset(cnt, 0, sizeof(cnt)); for(int i = n; i >= 1; i--){ for(int j = P[i].height; j >= 1; j--){ temp[j] = {cnt[j], j}; } sort(temp + 1, temp + 1 + P[i].height, custom_cmp); for(int j = 1; j <= P[i].numSail; j++){ ans1 += temp[j].fi; cnt[temp[j].se]++; } } int ans2 = 0; memset(cnt, 0, sizeof(cnt)); for(int i = 1; i <= n; i++){ for(int j = P[i].height; j >= 1; j--){ temp[j] = {cnt[j], j}; } sort(temp + 1, temp + 1 + P[i].height, custom_cmp); for(int j = 1; j <= P[i].numSail; j++){ ans2 += temp[j].fi; cnt[temp[j].se]++; } } cout << min(ans1, ans2) << endl; } } void solve(){ // if (subtask1::check()) return subtask1::solve(); if (subtask2::check()) return subtask2::solve(); } main() { fast; if (fopen(TASKNAME".inp","r")){ freopen(TASKNAME".inp","r",stdin); freopen(TASKNAME".out","w",stdout); } input(); solve(); } /** Warning: - MLE / TLE? - Gioi han mang? - Gia tri max phai luon gan cho -INF - long long co can thiet khong? - tran mang. - code can than hon **/

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

sails.cpp:136:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  136 | main()
      | ^~~~
sails.cpp: In function 'int main()':
sails.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...