Submission #40267

#	Time	Username	Problem	Language	Result	Execution time	Memory
40267		OneSubmissionMan	Split the sequence (APIO14_sequence)	C++11	0 / 100	7 ms	20608 KiB

sequence

# include <bits/stdc++.h>

# define F first
# define S second
# define mp make_pair
// everything go according to my plan
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
void localInput (string in = "s") {
  if (fopen (in.c_str(), "r"))
    freopen (in.c_str(), "r", stdin);
  else
    cerr << "Input file not found" << endl;
}
int n;

int k;

int a[Sz];

bool sep[Sz];

int nxt[Sz], prv[Sz];

int pref[Sz];

ll ans;

vec<int> splits;

int main()
{  	      
	localInput();
  Read_rap ();
  cin >> n >> k;
  for (int i = 1; i <= n; i++)	
  	cin >> a[i];

  for (int i = 1; i <= n + 1; i++)
  	pref[i] = pref[i - 1] + a[i];
                                
  for (int i = 1; i <= n; i++)
  	nxt[i] = n;
  sep[n] = 1;
  	
	for (int s = 1; s <= k; s++) {
		ll mx = 0;
		int newSep = 0;
		for (int i = 1; i <= n; i++) {
			if (sep[i])	continue;        
			int x = pref[i] - pref[prv[i]];
			int y = pref[nxt[i]] - pref[i];
			ll prod = x * 1ll * y;
			if (prod >= mx) {
				mx = prod;
				newSep = i;
			}
		}
		sep[newSep] = 1;
		ans += mx;      

		splits.pb (newSep);

		for (int i = 1; i <= n; i++)
			if (sep[i])	prv[i] = i;
				else
					prv[i] = prv[i - 1];

		for (int i = n - 1; i >= 1; i--)
			if (sep[i])	nxt[i] = i;
				else
					nxt[i] = nxt[i + 1];
	}
	cout << ans << endl;
	for (int k : splits)
		cout << k << ' ';
  	
  return 0;
}










// Coded by Z..

Compilation message (stderr)

sequence.cpp: In function 'void files(std::__cxx11::string)':
sequence.cpp:37:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen ((problem + ".in").c_str(),"r",stdin);
                                                  ^
sequence.cpp:38:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen ((problem + ".out").c_str(),"w",stdout);
                                                    ^
sequence.cpp: In function 'void localInput(std::__cxx11::string)':
sequence.cpp:43:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen (in.c_str(), "r", stdin);
                                     ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29