Submission #1035317

#TimeUsernameProblemLanguageResultExecution timeMemory
1035317RequiemSailing Race (CEOI12_race)C++17
0 / 100
3094 ms9824 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 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 endl '\n' #define pi 3.14159265359 #define TASKNAME "sailrace" 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 = 3e5 + 9; string str; int n, k; vector<int> g[MAXN]; void extract(int curId){ int num = 0; // cout << str << endl; str = str + ' '; for(int i = 0; i < str.length(); i++){ if (str[i] != ' ') { num = num * 10 + (str[i] - '0'); // cout << num << ' ' << str[i] - '0' << endl; } else { if (num != 0) { g[curId].pb(num); // cout << curId << ' ' << num << endl; } else break; num = 0; } } } namespace subtask1{ bool check(){ return k == 0; } int dp[2][502][502], backward = 0; int goBack(int id){ return (id - backward <= 0) ? id - backward + n : (id - backward); } int goUp(int id){ return (id + backward) - ((id + backward > n) ? (n) : 0); } int memo(int state, int Larc, int Rarc){ int mx = 0; for(int len = n; len >= 1; len--){ for(int Larc = 1, Rarc = Larc + len - 1; Rarc <= n; Rarc++, Larc++){ for(int state = 0; state < 2; state++){ int cur = goUp((state) ? Rarc : Larc); if (dp[state][Larc][Rarc] < 0) continue; // cout << cur << ' ' << state << ' ' << Larc << ' ' << Rarc << ' ' << dp[state][Larc][Rarc] << endl; if (state == 0){ for(auto v: g[cur]){ int curV = goBack(v); if (curV > Larc and curV <= Rarc) { // maximize(dp[0][Larc][Rarc], 1 + max(memo(0, curV, Rarc), memo(1, Larc + 1, curV))); maximize(dp[0][curV][Rarc], dp[0][Larc][Rarc] + 1); maximize(dp[1][Larc + 1][curV], dp[0][Larc][Rarc] + 1); } } } else{ for(auto v: g[cur]){ int curV = goBack(v); if (curV >= Larc and curV < Rarc) { // maximize(dp[1][Larc][Rarc], 1 + max(memo(0, curV, Rarc - 1), memo(1, Larc, curV))); maximize(dp[0][curV][Rarc - 1], dp[1][Larc][Rarc] + 1); maximize(dp[1][Larc][curV], dp[1][Larc][Rarc] + 1); } } } } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ maximize(mx, dp[0][i][j]); maximize(mx, dp[1][i][j]); } } return mx; } void solve(){ int bestI = 0, res = 0; for(int i = 1;i <= n; i++){ memset(dp, -0x3f, sizeof(dp)); backward = i - 1; dp[0][1][n] = 0; int mx = memo(0, 1, n); if (maximize(res, mx)){ bestI = i; } } cout << res << endl; } } main() { fast; if (fopen(TASKNAME".inp","r")){ freopen(TASKNAME".inp","r",stdin); freopen(TASKNAME".out","w",stdout); } cin >> n >> k; cin.ignore(); for(int i = 1; i <= n; i++){ getline(cin, str); extract(i); } if (subtask1::check()) return subtask1::solve(), 0; subtask1::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 - Nho sinh test de tranh RTE / TLE --> Coi lai truoc khi nop **/

Compilation message (stderr)

race.cpp: In function 'void extract(int)':
race.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |      for(int i = 0; i < str.length(); i++){
      |                     ~~^~~~~~~~~~~~~~
race.cpp: In function 'void subtask1::solve()':
race.cpp:109:13: warning: variable 'bestI' set but not used [-Wunused-but-set-variable]
  109 |         int bestI = 0, res = 0;
      |             ^~~~~
race.cpp: At global scope:
race.cpp:123:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  123 | main()
      | ^~~~
race.cpp: In function 'int main()':
race.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...