Help needed — ABC-175 D Sample test cases pass but submission fails

Revision en1, by Hustle_Loyalty_Respect, 2020-11-15 15:44:05

Link to problem — https://atcoder.jp/contests/abc175/tasks/abc175_d

Link to my submission: https://atcoder.jp/contests/abc175/submissions/18135753

I am not able to figure out what's wrong in my logic — if the sum of cycle is positive, then I would think of doing as many cycles as possible until reaching k count because it only helps increase cost. Then using mod i can figure out what is the most optimum steps to take further to reach max in the last cycle.

All sample test cases pass but not the submission. Not able to understand why. Any kind of help appreciated


#include <bits/stdc++.h> using namespace std; using ll = long long; const int mod = 1e9 + 7; template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "(" << p.first << "," << p.second << ")"; return os; } template <class T> ostream& operator<<(ostream& os, const vector<T>& v) { os << "{"; for(int i = 0; i < v.size(); ++i) { if (i) os << ","; os << v[i]; } os << "}"; return os; } ll n, k; ll p[5005]; ll c[5005]; void solve() { cin >> n >> k; for(ll i=0; i<n; ++i) { cin >> p[i]; --p[i]; } for(ll j=0; j<n; ++j) { cin >> c[j]; } ll best = -1e17; for(ll node=0; node<n; ++node) { ll curr = node; vector<ll> pref; vector<ll> mx; do { curr = p[curr]; if(pref.empty()) pref.emplace_back(c[curr]); else pref.emplace_back(pref.back() + c[curr]); if(mx.empty()) mx.emplace_back(pref.back()); else mx.emplace_back(max(mx.back(), pref.back())); } while(curr != node); ll score = 0ll; ll cnt = k; ll cycle_sum = pref.back(); ll cycle_len = pref.size(); if(cycle_sum > 0 && cnt >= cycle_len) { score += (k / cycle_len) * cycle_sum; cnt = k % cycle_len; } if(cnt > 0) score += mx[cnt-1]; best = max(best, score); //cout << pref << endl << mx << endl << score << endl << endl; } cout << best << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--) solve(); return 0; }
Tags #atcoder, #beginner, #graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Hustle_Loyalty_Respect 2020-11-15 16:01:21 25
en1 English Hustle_Loyalty_Respect 2020-11-15 15:44:05 2416 Initial revision (published)