Submission #38286

#	Time	Username	Problem	Language	Result	Execution time	Memory
38286		mirbek01	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6000 ms	93828 KiB

subsequence

# include <bits/stdc++.h>

# define pb push_back
# define fr first
# define sc second
# define mk make_pair

using namespace std;

const long long linf = 1e18 + 7;
const int inf = 1e9 + 7;
const int N = 1e5 + 5;

typedef long long ll;

int n, a[N], k[N], bit[N], pr[N], M = 1024;
pair <int, int> dp[1024][1024][11], ans;
vector <int> res;

int main(){
      scanf("%d", &n);

      for(int i = 1; i <= n; i ++)
            scanf("%d", &a[i]);

      for(int i = 1; i <= n; i ++)
            scanf("%d", &k[i]);

      for(int i = 0; i < M; i ++)
            bit[i] = __builtin_popcount(i);

      for(int i = 1; i <= n; i ++){
            int pref = a[i] >> 10, suff = a[i] % M, cur = 1, p = 0;
            for(int mask = 0; mask < M; mask ++){
                  int need = k[i] - bit[mask & pref];
                  if(need < 0 || need > 10) continue;
                  if(cur < dp[mask][suff][need].fr + 1)
                        cur = dp[mask][suff][need].fr + 1, p = dp[mask][suff][need].sc;
            }
            pr[i] = p;
            for(int mask = 0; mask < M; mask ++){
                  int need = bit[mask & suff];
                  if(need < 0 || need > 10) continue;
                  if(dp[pref][mask][need].fr < cur)
                        dp[pref][mask][need] = mk(cur, i);
            }
            if(ans.fr < cur)
                  ans = mk(cur, i);
      }

      while(ans.sc){
            res.pb(ans.sc);
            ans.sc = pr[ans.sc];
      }

      reverse(res.begin(), res.end());

      printf("%d\n", res.size());

      for(int i : res)
            printf("%d ", i);
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:58:32: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
       printf("%d\n", res.size());
                                ^
subsequence.cpp:21:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
                      ^
subsequence.cpp:24:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i]);
                               ^
subsequence.cpp:27:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &k[i]);
                               ^

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 60