Submission #300620

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
300620	2020-09-17T10:31:21 Z	MarcoMeijer	Carnival Tickets (IOI20_tickets)	C++14	Compilation error	0 ms	0 KB

tickets

#include <bits/stdc++.h>
#include "tickets.h"

using namespace std;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<ii> vii;

const int INF=1e9;
const int MX=1505;

int n, k, m;
vvi X;
vvi answer;
vvll dp;
vvll dpOpt;
ll cost[MX][MX];
int big[MX];
int ticketBig[MX], ticketSmall[MX];

void searchDp(int x, int y) {
    if(x == 0) return;
    int opt = dpOpt[x][y];
    big[x-1] = opt;
    searchDp(x-1, y-opt);
}

ll find_maximum(int _k, vvi _x) {
    k = _k; X = _x;
    n = X.size();
    m = X[0].size();
    int totBig = (n/2)*k;

    // fill cost
    RE(i,n) {
        int sm = 0;
        RE(j,k) sm -= X[i][j];
        RE(j,k+1) {
            cost[i][j] = sm;
            if(j == k) break;
            sm += X[i][k-1-j];
            sm += X[i][m-1-j];
        }
    }

    // fill dp
    dp.assign(n+1,vi(totBig+1, -1e18));
    dpOpt.assign(n+1,vi(totBig+1, -1));
    dp[0][0] = 0;
    REP(i,1,n) RE(j,totBig+1) {
        RE(I,min(k+1,j+1)) {
            ll ndp = dp[i-1][j-I] + cost[i-1][I];
            if(ndp > dp[i][j]) {
                dp[i][j] = ndp;
                dpOpt[i][j] = I;
            }
        }
    }
    searchDp(n,totBig);

    // create answer
    ll ans = 0;
    answer.assign(n,vi(m,-1));
    RE(i,n) ticketBig[i]=m-1, ticketSmall[i]=0;
    RE(i,k) {
        vii best;
        RE(i,n) best.pb({big[i], i});
        sort(all(best), greater<ii>());
        RE(j,n/2) {
            int x = best[j].se;
            ans += X[x][ticketBig[x]];
            big[ticketBig[x]]--;
            answer[x][ticketBig[x]--] = i;
        }
        RE(j,n/2) {
            int x = best[j+n/2].se;
            ans -= X[x][ticketSmall[x]];
            answer[x][ticketSmall[x]++] = i;
        }
    }

    allocate_tickets(answer);
    return ans;
}

Compilation message

tickets.cpp: In function 'll find_maximum(int, vvi)':
tickets.cpp:61:32: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   61 |     dp.assign(n+1,vi(totBig+1, -1e18));
      |                                ^~~~~
tickets.cpp:61:38: error: no matching function for call to 'std::vector<std::vector<long long int> >::assign(int, vi)'
   61 |     dp.assign(n+1,vi(totBig+1, -1e18));
      |                                      ^
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from tickets.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:746:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<long long int>]'
  746 |       assign(size_type __n, const value_type& __val)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:746:47: note:   no known conversion for argument 2 from 'vi' {aka 'std::vector<int>'} to 'const value_type&' {aka 'const std::vector<long long int>&'}
  746 |       assign(size_type __n, const value_type& __val)
      |                             ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/9/bits/stl_vector.h:765:2: note: candidate: 'template<class _InputIterator, class> void std::vector<_Tp, _Alloc>::assign(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  765 |  assign(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:765:2: note:   template argument deduction/substitution failed:
tickets.cpp:61:38: note:   deduced conflicting types for parameter '_InputIterator' ('int' and 'std::vector<int>')
   61 |     dp.assign(n+1,vi(totBig+1, -1e18));
      |                                      ^
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from tickets.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:791:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::initializer_list<_Tp>) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  791 |       assign(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:791:7: note:   candidate expects 1 argument, 2 provided
tickets.cpp:62:38: error: no matching function for call to 'std::vector<std::vector<long long int> >::assign(int, vi)'
   62 |     dpOpt.assign(n+1,vi(totBig+1, -1));
      |                                      ^
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from tickets.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:746:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::vector<long long int>]'
  746 |       assign(size_type __n, const value_type& __val)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:746:47: note:   no known conversion for argument 2 from 'vi' {aka 'std::vector<int>'} to 'const value_type&' {aka 'const std::vector<long long int>&'}
  746 |       assign(size_type __n, const value_type& __val)
      |                             ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/9/bits/stl_vector.h:765:2: note: candidate: 'template<class _InputIterator, class> void std::vector<_Tp, _Alloc>::assign(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  765 |  assign(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:765:2: note:   template argument deduction/substitution failed:
tickets.cpp:62:38: note:   deduced conflicting types for parameter '_InputIterator' ('int' and 'std::vector<int>')
   62 |     dpOpt.assign(n+1,vi(totBig+1, -1));
      |                                      ^
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from tickets.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:791:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::initializer_list<_Tp>) [with _Tp = std::vector<long long int>; _Alloc = std::allocator<std::vector<long long int> >]'
  791 |       assign(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_vector.h:791:7: note:   candidate expects 1 argument, 2 provided