Submission #38301

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

subsequence

# include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

# 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[11][1024][1024], 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[need][mask][suff].fr + 1)
                        cur = dp[need][mask][suff].fr + 1, p = dp[need][mask][suff].sc;
            }
            pr[i] = p;
            for(int mask = 0; mask < M; mask ++){
                  int need = bit[mask & suff];
                  if(dp[need][pref][mask].fr < cur)
                        dp[need][pref][mask] = 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 = 0; i < res.size(); i ++)
            printf("%s%d", i ? " ":"", res[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:60:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < res.size(); i ++)
                        ^
subsequence.cpp:22:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &n);
                      ^
subsequence.cpp:25:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i]);
                               ^
subsequence.cpp:28: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: 60 / 60