oj.uz

Submission #135016

# Submission time Handle Problem Language Result Execution time Memory
135016 2019-07-23T14:23:45 Z CaroLinda Split the sequence (APIO14_sequence) C++14
0 / 100
 3 ms 508 KB 
#include <bits/stdc++.h>

#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int inf = 0x3f3f3f3f ;
const int MAXN = 12 ;

using namespace std ;

int n , k ;
vector<pii> intervals ;
ll pref[MAXN] , ans = 0 ;

ll get(int i , int j) { return pref[j] - pref[i-1] ; }

int main()
{

	scanf("%d%d", &n , &k ) ;
	lp(i,1,n+1) scanf("%lld", &pref[i] ) ;
	
	lp(i,1,n+1) pref[i] += pref[i-1] ;	

	intervals.pb( mk(1,n) ) ;

	lp(i,0,k)
	{
		
		pair<ll,int> ansK = mk(-1,-1) ;

		for( pii myInt : intervals )
			lp(j,myInt.ff , myInt.ss)
				ansK = max(ansK , mk(get(myInt.ff,j)*get(j+1, myInt.ss), j) ) ;
		
		lp(j,0,intervals.size())
			if( intervals[j].ff <= ansK.ff && intervals[j].ss >= ansK.ss )
			{
				int beg=intervals[j].ff, en=intervals[j].ss ;
				intervals[j] = mk(beg,ansK.ss) ;
				intervals.pb(mk(ansK.ss+1,en)) ; 
				break ;
			}

		ans += ansK.ff ;

	}

	printf("%lld\n" , ans ) ;

}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:3:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
sequence.cpp:41:6:
   lp(j,0,intervals.size())
      ~~~~~~~~~~~~~~~~~~~~       
sequence.cpp:41:3: note: in expansion of macro 'lp'
   lp(j,0,intervals.size())
   ^~
sequence.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n , &k ) ;
  ~~~~~^~~~~~~~~~~~~~~~~~
sequence.cpp:26:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  lp(i,1,n+1) scanf("%lld", &pref[i] ) ;
              ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -