oj.uz

Submission #580526

# Submission time Handle Problem Language Result Execution time Memory
580526 2022-06-21T11:46:05 Z myvaluska Kpart (eJOI21_kpart) C++14
10 / 100
 2000 ms 852 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(100029, -1);
            dp[0] = 1;
            for (int j = i; j < n; j++)
            {
                int d = j - i + 1;
                sum += v[j];
                for (int k = dp.size() - 1; k >= 0; k--)
                {
                    if (k - v[j] >= 0 && dp[k - v[j]] == 1)
                    {
                        dp[k] = 1;
                    }
                }
                /*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 << endl;
    }
    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:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i = 0; i < vys.size(); i++)
      |                         ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 804 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 70.0

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