oj.uz

Submission #580545

# Submission time Handle Problem Language Result Execution time Memory
580545 2022-06-21T12:09:01 Z myvaluska Kpart (eJOI21_kpart) C++14
30 / 100
 2000 ms 1072 KB 
// arc172.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int>v(n);
        for (int i = 0; i < n; i++)
        {
            cin >> v[i];
        }
        vector<vector<int>>ka(n, vector<int>(n,-1));///index,dlzka
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            vector<int>dp(50029, -1);
            dp[0] = 1;
            vector<int>dasa;///ide sa robit skareda optimalizacia:)))
            dasa.push_back(0);
            for (int j = i; j < n; j++)
            {
                int d = j - i + 1;
                sum += v[j];
                int x = dasa.size() - 1;
                for (int k=x;k>=0;k--)
                {
                    if (dp[dasa[k]+v[j]]==-1&&dasa[k]+v[j]<=dp.size())
                    {
                        dp[dasa[k]+v[j]] = 1;
                        dasa.push_back(dasa[k]+v[j]);
                    }
                }
                /*for (int i2 = 0; i2 <20; i2++)
                {
                    cout << dp[i2] << ' ';
                }*/
                ///cout << endl;
                if (sum % 2 == 0 && dp[sum / 2] == 1)
                {
                    ka[i][d - 1] = 1;
                    ///cout << "da sa " << i << ' ' << d - 1 << endl;
                }
            }
            
        }
        vector<int>vys;
        for (int i = 1; i < n + 1; i++)
        {
            int flag = 0;
            for (int j = 0; j < n; j++)
            {
                if (ka[j][i - 1] == -1&&n-j>=i)
                {
                    flag = 1;
                }
            }
            if (flag == 0)
            {
                vys.push_back(i);
            }
        }
        cout << vys.size() << ' ';
        for (int i = 0; i < vys.size(); i++)
        {
            cout << vys[i] << " ";
        }
        cout << "\n";
    }
    return 0;
    ///std::cout << "Hello World!\n";
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:41:59: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |                     if (dp[dasa[k]+v[j]]==-1&&dasa[k]+v[j]<=dp.size())
Main.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int i = 0; i < vys.size(); i++)
      |                         ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 572 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 600 KB Output is correct
2 Correct 606 ms 672 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2084 ms 1072 KB Time limit exceeded
2 Halted 0 ms 0 KB -