Submission #1035059

#TimeUsernameProblemLanguageResultExecution timeMemory
1035059RequiemSailing Race (CEOI12_race)C++17
30 / 100
3096 ms11568 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){ if (dp[state][Larc][Rarc] != -1) return dp[state][Larc][Rarc]; if (Larc >= Rarc) return 0; dp[state][Larc][Rarc] = 0; int cur = goUp((state) ? Rarc : Larc); if (state == 0){ for(auto v: g[cur]){ int curV = goBack(v); // cout << cur << ' ' << curV << ' ' << v << endl; if (curV > Larc and curV <= Rarc) { maximize(dp[0][Larc][Rarc], 1 + max(memo(0, curV, Rarc), memo(1, Larc + 1, curV))); } } } 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))); } } } // cout << state << ' ' << Larc << ' ' << Rarc << ' ' << dp[state][Larc][Rarc] << endl; return dp[state][Larc][Rarc]; } void solve(){ int bestI = 0, res = 0; for(int i = 1; i <= n; i++){ memset(dp, -1, sizeof(dp)); backward = i - 1; int mx = memo(0, 1, n); if (maximize(res, mx)){ bestI = i; } } cout << res << endl << bestI << 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; } /** 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(long long int)':
race.cpp:30:23: warning: comparison of integer expressions of different signedness: 'long long 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: At global scope:
race.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main()
      | ^~~~
race.cpp: In function 'int main()':
race.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...