QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#60552 | #2544. Flatland Currency | enh | WA | 230ms | 11512kb | C++14 | 2.8kb | 2022-11-05 15:16:19 | 2022-11-05 15:16:22 |
Judging History
answer
#include <iostream>
#include <vector>
using namespace std ;
#define int long long
const int N = 100005 , INF = 2e14 ;
int n , m , a[N] , b[N] ;
void ckin ( int &x , int y ) { x = min ( x , y ) ; }
vector < int > merge ( vector < int > a , vector < int > b ) {
int n = a .size ( ) , m = b .size ( ) ;
vector < int > c ( n + m - 1 ) ;
for ( int &i : c ) i = INF ;
static int x[N] , y[N] , z[N] ;
for ( int i = 0 ; i < 12 ; ++ i ) {
if ( i >= n ) break ;
for ( int j = 0 ; j < 12 ; ++ j ) {
if ( j >= m ) break ;
int t1 = 0 , t2 = 0 , t3 = 0 ;
for ( int k = i ; k < n ; k += 12 ) x [ t1 ++ ] = a [ k ] ;
for ( int k = j ; k < m ; k += 12 ) y [ t2 ++ ] = b [ k ] ;
for ( int k = t1 - 1 ; k ; -- k ) x [ k ] -= x [ k - 1 ] ;
for ( int k = t2 - 1 ; k ; -- k ) y [ k ] -= y [ k - 1 ] ;
int k1 = 1 , k2 = 1 ;
while ( k1 < t1 && k2 < t2 ) {
if ( x [ k1 ] > y [ k1 ] ) z [ ++ t3 ] = x [ k1 ++ ] ;
else z [ ++ t3 ] = y [ k1 ++ ] ;
}
while ( k1 < t1 ) z [ ++ t3 ] = x [ k1 ++ ] ;
while ( k2 < t2 ) z [ ++ t3 ] = y [ k2 ++ ] ;
z [ 0 ] = x [ 0 ] + y [ 0 ] ;
for ( int k = 1 ; k <= t3 ; ++ k ) z [ k ] += z [ k - 1 ] ;
for ( int k = 0 ; k <= t3 ; ++ k ) ckin ( c [ k * 12 + i + j ] , z [ k ] ) ;
}
}
return c ;
}
vector < int > solve ( int l , int r ) {
if ( l == r ) {
vector < int > f ( 5 ) ;
for ( int i = 1 ; i < 5 ; ++ i ) f [ i ] = INF ;
f [ 0 ] = 0 , f [ a [ l ] ] = b [ l ] ;
return f ;
}
int mid = ( l + r ) >> 1 ;
// vector < int > res = merge ( solve ( l , mid ) , solve ( mid + 1 , r ) ) ;
// cout << " solve : " << l << " - " << r << " : " << mid << "\n" ;
// int siz = res .size ( ) ;
// cout << " siz : " << siz << "\n" ;
// for ( int u : res ) cout << u << " " ;
// puts ( "\n\n" ) ;
// return res ;
return merge ( solve ( l , mid ) , solve ( mid + 1 , r ) ) ;
}
int read ( ) {
char ch = getchar ( ) ;
int x = 0 ;
while ( ch < '0' || ch > '9' )
ch = getchar ( ) ;
while ( ch >= '0' && ch <= '9' )
x = x * 10 + ch - 48 , ch = getchar ( ) ;
return x ;
}
signed main ( ) {
// freopen ( "data.in" , "r" , stdin ) ;
// freopen ( "data.out" , "w" , stdout ) ;
cin >> n >> m ;
int nn = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
int x = read ( ) ;
if ( x % 5 == 0 ) continue ;
b [ ++ nn ] = ( x + 4 ) / 5 * 5 ;
a [ nn ] = b [ nn ] - x ;
}
n = nn ;
// cout << " a : " ;
// for ( int i = 1 ; i <= n ; ++ i ) printf ( "%3d" , a [ i ] ) ;
// puts ( "" ) ;
// cout << " b : " ;
// for ( int i = 1 ; i <= n ; ++ i ) printf ( "%3d" , b [ i ] ) ;
// puts ( "" ) ;
vector < int > ans = solve ( 1 , n ) ;
int siz = ans .size ( ) , res = 0 ;
for ( int i = 0 ; i < siz ; ++ i )
if ( ans [ i ] <= m ) res = i ;
cout << res + m % 5 << "\n" ;
return 0 ;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5372kb
input:
5 57 9 14 31 18 27
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 2ms
memory: 5372kb
input:
4 50 11 11 11 11
output:
12
result:
ok answer is '12'
Test #3:
score: -100
Wrong Answer
time: 230ms
memory: 11512kb
input:
100000 89648823509660 921733427 402270498 51157221 585477094 435728758 913951087 580580944 557082810 585086423 837912728 799129405 867009344 751591136 714946046 464999915 256043168 416678301 183246216 569365122 479031618 435168577 31068363 903791719 497652990 960987871 223120213 395437892 112869678 ...
output:
130
result:
wrong answer expected '200414', found '130'