akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <functional>
#include <iomanip>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

// #define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _fromto2(i,n) for(int i=0;i<=(n);++i)
#define _fromto3(i,a,b) for(int i=(a);i<=(b);++i)
#define fromto(...) _overload3(__VA_ARGS__,_fromto3,_fromto2,)(__VA_ARGS__)

#define rrep(i,n) for(int i=(n);i>=0;--i)
#define iter(it,v) for(auto it=v.begin();it!=v.end();++it)
const int MOD = 1e9+7;
const ll INF = 1e18;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

// debug
template<class T>ostream& operator<<(ostream& os, vector<T>& vec){os<<"{";for(int i=0;i<vec.size();++i)os<<(i?", ":"")<<vec[i];os<<"}";return os;}
template<class T1,class T2>ostream& operator<<(ostream& out,const pair<T1,T2>& rhs){out<<"("<<rhs.first<<", "<<rhs.second<<")";return out;}
#include<type_traits>
template<typename T,size_t SIZE,enable_if_t<!is_same<remove_cv_t<T>,char>::value,nullptr_t> = nullptr>ostream& operator<<(ostream& os,T(&arr)[SIZE]){os<<"{";for(size_t i=0;i<SIZE;++i)os<<(i?", ":"")<<arr[i];os<<"}";return os;}
#ifdef LOCAL
    #define debug(v) cerr<<v<<"\n"
#else
    #define debug(...) 42
#endif


int main() {
  int N, M, L; cin >> N >> M >> L;

  ll d[N][N], d2[N][N];
  rep(i, N) rep(j, N) {
    d[i][j] = d2[i][j] = INF;
  }
  rep(i, M) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    d[a][b] = d[b][a] = c;
  }
  rep(k, N) rep(i, N) rep(j, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  rep(i, N) rep(j, N) {
    if (d[i][j] <= L)
      d2[i][j] = 1;
  }
  rep(k, N) rep(i, N) rep(j, N) d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);

  int Q; cin >> Q;
  rep(i, Q) {
    int s, t;
    cin >> s >> t;
    --s, --t;
    if (d2[s][t] == INF)
      cout << "-1\n";
    else
      cout << d2[s][t]-1 << endl;
  }

  return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;

int main() {
  string s;
  cin>>s;
  sort(s.begin(),s.end());
  if(s[0]=='a' && s[1]=='b' && s[2]=='c') cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#define ll long long
#define MAX 25 * 1e13
#define N  200010

#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define EB(X) emplace_back(X)
#define REP(i,a) for(int i=0;i<(a);++i)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()
#define VI vector<int>;

using namespace std;
int MOD = 1000000007;


ll gcd(ll a,ll b){
  if( b == 0 ) return a;
  return gcd(b,a%b);
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  cin >> n;
  ll ret = 0;
  for (int i = 1; i <= n; i++ ){
    for(int j = 1; j <= n ; j++ ){
      for(int k = 1 ; k <= n ; k++ ){
        if( i == j && j == k ) {
          ret += i;
          continue;
        }
        else{
          ret += gcd(gcd(i,j),k);
        }
      }
    }
  }
  cout << ret << endl;

  return 0;
}



Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;

using ll =  long long;
using pint =  pair<int,int>;

#define INF 99999999
#define rep(i,n) for(int (i)=0,temp=(int)(n);(i)<temp;++(i)) 
#define repi(i,start,end) for(int (i)=(start),temp=(int)(end);i<(end);++(i))
#define rfor(v,x) for(const auto& (x) : (v)) //xは値を表す
#define all(x) (x).begin(),(x).end()
#define SORT(v, n) sort((v), (v)+(n))
#define vsort(v) sort((v).begin(), (v).end())
#define vfsort(v,lambda) sort(all((v)),(lambda))
#define vint vector<int>
#define vvint vector<vector<int>> //vvint v(n,vint(n))のように宣言できる
#define vin(v) rep(i,(v).size()) {cin >> (v)[i];}
//最終奥義(使うときはINFも書き換えろ!!)
//#define int long long
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ctoi(char c) {return c-'0';}
//lambda式 -> [&](int x, int y){return x<y;}
//vector内の重複を削除-> v.erase(unique(all(v)),v.end());

int n;
char ton(char c){
  if(c+n<='Z')return c+n;
  else return ('A'+(n-('Z'-c+1)));
}

signed main(void){
  cin >>n;
  string s;cin >> s;
  string ans;ans.resize(s.size());
  rep(i,s.size()){
    ans[i] = ton(s[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <set>
#include <vector>

using namespace std;

   int N;
   vector<string> W;

int main() {
   cin >> N;
   for (int i=1;i<=N;i++) {
      string word;
      cin >> word;
      W.push_back(word);
   }
   for (int i=1;i<N;i++) {
      if (W[i-1][W[i-1].size()-1] != W[i][0]) {
         cout << "No" << endl;
         return 0;
      }
   }
   set<string> set(W.begin(), W.end());
   if (set.size() != N) {
      cout << "No" << endl;
      return 0;
   }
   cout << "Yes" << endl;
   return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>
#include <utility>
#define sign(a) ((a>0)-(a<0))
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define LL long long
#define INF (LL)(1LL<<60)
#define all(a) a.begin(), a.end()
#define gr greater<LL>()

using namespace std;


void solve(long long N, std::vector<long long> A, std::vector<long long> B){
    LL ans=0,left=A[0];
    rep(i, N){
        LL lattack = min(left, B[i]);
        LL nrem = B[i]-lattack;
        LL rattack = min(nrem, A[i+1]);
        ans += (lattack+rattack);
        left = A[i+1]-rattack;
    }
    cout << ans << endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N+1);
    for(int i = 0 ; i < N+1 ; i++){
        scanf("%lld",&A[i]);
    }
    std::vector<long long> B(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&B[i]);
    }
    solve(N, std::move(A), std::move(B));
    return 0;
}


Measured memory_bytes: 1920
#include <stdio.h>
#include <stdlib.h>

int main()
{
	long long N;
	scanf("%lld", &N);
	
	int n, sum = 0, ans;
	for (n = 1; N >= 10; n++, N /= 10) sum += N % 10;
	
	if (n == 1) ans = N;
	else if (sum == (n - 1) * 9) ans = sum + N;
	else ans = (n - 1) * 9 + N - 1;
	
	printf("%d\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template<u32 M = 1000000007>
struct modint{
    u32 val;
    modint(): val(0){}
    template<typename T>
    modint(T t){t %= (T)M; if(t < 0) t += (T)M; val = t;}

    modint pow(ll k) const {
        modint res(1), x(val);
        while(k){
            if(k&1) res *= x;
            x *= x;
            k >>= 1;
        }
        return res;
    }
    template<typename T>
    modint& operator=(T t){t %= (T)M; if(t < 0) t += (T)M; val = t; return *this;}
    modint inv() const {return pow(M-2);}
    modint& operator+=(modint a){val += a.val; if(val >= M) val -= M; return *this;}
    modint& operator-=(modint a){if(val < a.val) val += M-a.val; else val -= a.val; return *this;}
    modint& operator*=(modint a){val = (u64)val*a.val%M; return *this;}
    modint& operator/=(modint a){return (*this) *= a.inv();}
    modint operator+(modint a) const {return modint(val) +=a;}
    modint operator-(modint a) const {return modint(val) -=a;}
    modint operator*(modint a) const {return modint(val) *=a;}
    modint operator/(modint a) const {return modint(val) /=a;}
    modint operator-(){return modint(M-val);}
    bool operator==(const modint a) const {return val == a.val;}
    bool operator!=(const modint a) const {return val != a.val;}
    bool operator<(const modint a) const {return val < a.val;}
};
using mint = modint<MOD>;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    mint ans = 0;
    for (auto &&i : v) scanf("%d", &i);
    sort(v.begin(),v.end(), greater<>());
    mint val = mint(2).pow(2*n-2);
    for (int i = 0; i < n; ++i) {
        ans += mint(v[i])*val*mint(i+2);
    }
    cout << ans.val << "\n";
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define show(x) for(auto i: x){cout << i << " ";}
#define showm(m) for(auto i: m){cout << m.x << " ";}
typedef long long ll;
typedef pair<int, int> P;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


#define N_MAX 100050
int ans_num[N_MAX] = {0};

int main()
{
    int n, k, q;
    cin >> n >> k >> q;
    rep(i, q){ int tmp; cin >> tmp; ans_num[--tmp]++;}

    rep(i, n){
        if (k - q + ans_num[i] > 0) puts("Yes");
        else puts("No");
    }

}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n,0);

    cin >> a.at(0);
    for(int i=1;i<n;i++){
        int input;
        cin >> input;
        a.at(i) = a.at(i-1)+input;
    }

    sort(a.begin(),a.end());

    long long ans=0;
    long long sirial=0;

    for(int i=0;i<n-1;i++){
        if(a.at(i)==0)ans++;
        if(a.at(i)==a.at(i+1))sirial++;
        else {
            ans += sirial*(sirial+1)/2;
            sirial=0;
        }
    }

    if(a.at(n-1)==0)ans++;
    ans += sirial*(sirial+1)/2;

    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <string>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <iostream>
#include <functional>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <cmath>
#include <limits>
#include <tuple>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()

int main()
{
	string S;
	cin >> S;
	if (S.size() == 3)
		reverse(S.begin(), S.end());
	cout << S << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
//const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    int zero = 0, one = 0;
    rep(i, s.size()) if (s[i] == '0') zero++; else one++;
    cout << s.size() - abs(zero - one) << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int n,q,l[N],r[N],ind;ll pre[N];
vector<int> g[N];
void dfs(int v,int fa){
    ++ind;l[v]=ind;
    for(auto u:g[v]){
        if(u==fa)continue;
        dfs(u,v);
    }
    r[v]=ind;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,1);
//    for(int i=1;i<=n;i++){
//        cout<<l[i]<<' '<<r[i]<<endl;
//    }
    int id,val;
    while (q--){
        cin>>id>>val;
        pre[l[id]]+=val;
        pre[r[id]+1]-=val;
    }
//    for(int i=1;i<=ind;i++){
//        cout<<pre[i]<<' ';
//    }
//    cout<<endl;
    for(int i=1;i<=ind+1;i++){
        pre[i]+=pre[i-1];
    }
//    for(int i=1;i<=ind;i++){
//        cout<<pre[i]<<' ';
//    }
//    cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<pre[l[i]]<<' ';
    }
}

Measured memory_bytes: 25856
#include <bits/stdc++.h>
using namespace std;

int main(int args, char *argv[])
{
  int N, A;

  cin >> N;
  cin >> A;

  if (N % 500 <= A)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>
#include <cassert>

using namespace std;

/* template */

using ll = long long;

void debug_out() { std::cout << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

#define rep(i, a, n) for (int i = (int)(a); i < (int)(n); i++)
#define rrep(i, a, n) for (int i = ((int)(n)-1); i >= (int)(a); i--)
#define Rep(i, a, n) for (long long i = (long long)(a); i< (long long)(n); i++)
#define RRep(i, a, n) for (long long i = ((long long)(n)-1); i>=(long long)(a); i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    int weight;
    edge(int f,int t,int w) : from(f), to(t), weight(w){ }
};


using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

template <class T>
inline bool chmin(T &a, T b){
    if (a > b){
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmax(T &a, T b){
    if (a < b){
        a = b;
        return true;
    }
    return false;
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

bool isPalindrome(string s){
    string t = s;
    reverse(all(t));
    return s==t;
}

constexpr ll INF = 1e18;

vector<int> dx = {-1,0,1,0};
vector<int> dy = {0,-1,0,1};

/* template */

vector<int> bfs(int s,const graph &g){
    int _size = g.size();
    vector<int> c(_size,-1);
    c[s] = 0;
    queue<int> que;
    que.push(s);
    while(!que.empty()){
        int x = que.front();
        que.pop();
        for(auto nx: g[x]){
            if(c[nx]<0){
                que.push(nx);
                c[nx] = c[x]+1;
            }
        }
    }
    return c;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    graph g(n);
    rep(i,0,n-1){
        int a,b; cin >> a >> b;
        a--; b--;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    vector<int> fennec = bfs(0,g);
    vector<int> snuke = bfs(n-1,g);
    int fe = 0, sn = 0;
    rep(i,0,n){
        if(fennec[i]<=snuke[i]) fe++;
        else sn++;
    }
    if(fe>sn){
        cout << "Fennec" << endl;
    }
    else{
        cout << "Snuke" << endl;
    }
}

Measured memory_bytes: 6528
#include "bits/stdc++.h"
using namespace std;
#define ASC(vec) vec.begin(), vec.end()			// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(i = 0; i < n; i++)
const long long INF = 1LL << 60;
typedef long long ll;

int main()
{
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;

	int dx = x2 - x1;
	int dy = y2 - y1;

	int x = x2;
	int y = y2;
	
	for (int i = 0; i < 2; i++)
	{
		swap(dx, dy);
		dx = -dx;
		x += dx;
		y += dy;
		cout << x << " " << y << " ";
	}
	cout << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	long long n, m, i, j, k, s, sx, sy, MOD = 1000000007, ans;
	cin >> n >> m;
	vector<long long> x(n), y(m);
	for (i = 0; i < n; i++) {
		cin >> x[i];
		if (i > 0) x[i] -= x[0];
	}
	x[0] = 0;
	for (i = 0; i < m; i++) {
		cin >> y[i];
		if (i > 0) y[i] -= y[0];
	}
	y[0] = 0;

	s = 0;
	sx = 0;
	for (i = 0; i < n; i++) {
		sx = (sx + (i * x[i] - s)) % MOD;
		s += x[i];
	}

	s = 0;
	sy = 0;
	for (i = 0; i < m; i++) {
		sy = (sy + (i * y[i] - s)) % MOD;
		s += y[i];
	}

	ans = (sx * sy) % MOD;
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  string s;
  cin >> s;

  if (s[2] == s[3] && s[4] == s[5]) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;

int main()
{
    int p,q,r;
    cin>>p;
    cin>>q;
    cin>>r;
    if(p+q>=p+r&&p+r<=q+r)
    {
        cout<<p+r;
    }
    else if(p+r>=p+q&&p+q<=q+r)
    {
        cout<<p+q;
    }
    else
    {
        cout<<q+r;
    }
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

const int N = 123456;
ll fact[N];

int main(void){
  ll n, m;
  cin >> n >> m;
  fact[0] = 1;
  REP(i, 1, N) {
    fact[i] = fact[i - 1] * i % mod;
  }
  if (abs(n - m) >= 2) {
    cout << 0 << endl;
    return 0;
  }
  if (n != m) {
    cout << fact[n] * fact[m] % mod << endl;
  } else {
    cout << 2 * fact[n] * fact[m] % mod << endl;
  }
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mod 1000000007
#define wi while
#define vl vector<ll>
#define vi vector<int>
#define map map<char,ll>
#define endl "\n"
const int mxN = 200001;
#define int unsigned long long int
int t[102][100001];
int knapsack(int a[],int val[],int n,int w)
{
    if(n==0||w==0)
        return 0;
    if(t[n][w]!=-1)
        return t[n][w];
    if(a[n]<=w)
    {
        return t[n][w]=max(val[n]+knapsack(a,val,n-1,w-a[n]),
            knapsack(a,val,n-1,w));

    }
    else
        return t[n][w]=knapsack(a,val,n-1,w);
}
signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    int n,w;
    cin>>n>>w;
    memset(t,-1,sizeof(t));

    int a[n+1],val[n+1];
    for(int i=1;i<=n;++i)
    {
        cin>>a[i]>>val[i];
    }
    int ans = knapsack(a,val,n,w);
    cout<<ans<<endl;
    
    return 0;

}


Measured memory_bytes: 83308
#include "bits/stdc++.h"
using namespace std;
int main() {
  cin.tie(0); ios_base::sync_with_stdio(false);
  int N, x; cin >> N >> x;
  int a[N]; for (int i{0}; i < N; ++i) cin >> a[i];
  sort(a, a + N);
  int i;
  for (i = 0; i < N; ++i) {
    x -= a[i];
    if (x < 0) break;
  }
  if (i == N && x > 0) --i;
  cout << i << "\n";
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
 public class abc084C {

 }

 */
public class Main {
  public void solve() throws FileNotFoundException {
    InputStream inputStream = System.in;

    InputHelper in = new InputHelper(inputStream);

    // actual solution
    int n = in.readInteger();

    int[] c = new int[n];
    int[] s = new int[n];
    int[] f = new int[n];


    for (int i = 0; i < n - 1; i++) {
      c[i] = in.readInteger();
      s[i] = in.readInteger();
      f[i] = in.readInteger();
    }

    for (int i = 0; i < n - 1; i++) {
      int cv = 0;
      for (int j = i; j < n - 1; j++) {
        if (s[j] >= cv) {
          cv = s[j] + c[j];
          continue;
        } else {
          int diff = cv - s[j];
          int t = (diff + f[j] - 1) / f[j];
          cv = s[j] + t * f[j] + c[j];
        }
      }
      System.out.println(cv);
    }
    
    System.out.println(0);
    // end here
  }

  public static void main(String[] args) throws FileNotFoundException {
    (new Main()).solve();
  }

  class InputHelper {
    StringTokenizer tokenizer = null;
    private BufferedReader bufferedReader;

    public InputHelper(InputStream inputStream) {
      InputStreamReader inputStreamReader = new InputStreamReader(inputStream);
      bufferedReader = new BufferedReader(inputStreamReader, 16384);
    }

    public String read() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          String line = bufferedReader.readLine();
          if (line == null) {
            return null;
          }
          tokenizer = new StringTokenizer(line);
        } catch (IOException e) {
          e.printStackTrace();
        }
      }

      return tokenizer.nextToken();
    }

    public Integer readInteger() {
      return Integer.parseInt(read());
    }

    public Long readLong() {
      return Long.parseLong(read());
    }
  }
}


Measured memory_bytes: 22100
#include <bits/stdc++.h>
#define int long long int
#define ll long long int
#define ld long double
#define getFaster ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define rep(i, init, n) for (int i = init; i < (int)n; i++)
#define rev(i, n, init) for (int i = (int)n; i >= init; i--)
#define MOD1 1e9 + 7
#define MOD2 998244353
#define f first
#define s second
#define endl '\n'
#define pii pair<int, int>
#define piii pair<pii, int>
#define precise(i) cout << fixed << setprecision(i)
#define codejam cout << "Case #" << ii + 1 << ": ";
#define impossible cout << "IMPOSSIBLE" << endl;
#define error(s) throw runtime_error(s)
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
int myRand(int R){int val=rng()%R;assert(val >= 0);return val;}

const long double PI = atan(1.0) * 4;
const int64_t INF64 = 3e18;
const int32_t INF32 = 2e9 + 7;
const int32_t LOG = 21;
const int32_t MOD = MOD1;

using namespace std;


//-------------------DEBUGGING-------------------------
void my_debugger(string s,int LINE_NUM){cerr<<endl;}
template<typename start,typename... end>
void my_debugger(string s,int LINE_NUM,start x,end... y) 
{
    if(s.back()!=',') {s+=',';cerr<<"LINE("<<LINE_NUM<<"): ";}
    int i=s.find(',');
    cerr<<s.substr(0,i)<<" = "<<x;
    s=s.substr(i+1);
    if(!s.empty()) cerr<<", ";
    my_debugger(s,LINE_NUM,y...);
}

#ifdef AJIT
#define debug(...) my_debugger(#__VA_ARGS__,__LINE__,__VA_ARGS__);
#else
#define debug(...) ;
#endif

//-----------------------------------------------------


int32_t main()
{
      getFaster;
      //files_init();
      int tests = 1;
      //cin >> tests;
      rep(ii, 0, tests)
      {
            int max1=0,max2=0;
             int n;
             cin>>n;
             vector<pii> v(n);
             rep(i,0,n)
             cin>>v[i].f>>v[i].s;
             sort(v.begin(),v.end());
             max1=-v[0].f-v[0].s;
             max2=-v[0].f+v[0].s;
             int ans=0;
             rep(i,1,n)
             {
                   ans=max({ans,v[i].f+v[i].s+max1,v[i].f-v[i].s+max2});
                   max1 = max(max1,-v[i].f - v[i].s);
                   max2 = max(max2,-v[i].f + v[i].s);
             }
             cout<<ans<<endl;
      }
      return 0;
}


Measured memory_bytes: 6388
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Node
{
    int i, j, k;
    ll Sum;

    Node(int i = 0, int j = 0, int k = 0, ll Sum = 0) : i(i), j(j), k(k), Sum(Sum) {}

    bool operator < (const Node& Other) const
    {
        return Sum < Other.Sum;
    }
};

int main()
{
    int x, y, z, k; cin >> x >> y >> z >> k;

    vector <ll> a(x);
    vector <ll> b(y);
    vector <ll> c(z);

    for(ll& A : a) cin >> A;
    for(ll& B : b) cin >> B;
    for(ll& C : c) cin >> C;

    sort(a.begin(), a.end(), greater <ll> ());
    sort(b.begin(), b.end(), greater <ll> ());
    sort(c.begin(), c.end(), greater <ll> ());

    vector <ll> Ans;

    priority_queue <Node> q;
    q.push(Node(0, 0, 0, a[0] + b[0] + c[0]));

    map <pair <pair <int,int>, int>, bool> Vis;

    while(Ans.size() < k)
    {
        Node node = q.top();    q.pop();

        if(Vis.count({{node.i, node.j},node.k})) continue;

        Vis[{{node.i, node.j},node.k}] = true;

        Ans.push_back(node.Sum);

        if(node.i + 1 < x)  q.push(Node(node.i + 1, node.j, node.k, a[node.i + 1] + b[node.j] + c[node.k]));
        if(node.j + 1 < y)  q.push(Node(node.i, node.j + 1, node.k, a[node.i] + b[node.j + 1] + c[node.k]));
        if(node.k + 1 < z)  q.push(Node(node.i, node.j, node.k + 1, a[node.i] + b[node.j] + c[node.k + 1]));
    }

    for(ll x : Ans) cout << x << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n, m;
	
	while(cin >> n){
		int a[100];
		for(int i = 0; i < n; i++)
			cin >> a[i];
		int ans = 0;	
		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++)
				ans += a[i] * a[j];
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <string.h>

#include <algorithm>
#include <cstdlib>  // abs() for integer
#include <iostream>

using namespace std;

int main(void) {
  int K;
  cin >> K;

  int ans = -1;

  int t = 7;
  int cnt;
  int i = 1;  // i項目

  while (i <= 1000000) {
    if (t % K == 0) {
      ans = i;
      break;
    }

    t = (t * 10 + 7) % K;

    i++;
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3676
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int main() {
    int a, b;
    cin >> a >> b;
    if (a == b) {
        cout << "Draw" << endl;
    }
    else if (a == 1) {
        cout << "Alice" << endl;
    }
    else if (b == 1) {
        cout << "Bob" << endl;
    }
    else if (a > b) {
        cout << "Alice" << endl;
    }
    else {
        cout << "Bob" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
  int n,x;
  int count=0;
  cin >> n >> x;
  int a[n];

  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
  }

  sort(a,a+n);

  for (int i = 0; i < n; i++)
  {
    x = x - a[i];
    if (x<0)
    {
      break;
    }else if(x==0)
    {
      count++;
      break;
    }
    count++; 
  }
  if (x>0)
  {
    count--;
  }
  
  

  cout << count << "\n";

  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

string A,B,C;

int main()
{
	cin>>A>>B>>C;
	int a=0,b=0,c=0;
	char x='a';
	while(1)
	{
		if(x=='a')
		{
			x=A[a];
			a++;
			if(A.length()<a)
			{
				cout<<'A'<<endl;
				return 0;
			}
		}
		else
		{
			if(x=='b')
			{
				x=B[b];
				b++;
				if(B.length()<b)
				{
					cout<<'B'<<endl;
					return 0;
				}
			}
			else
			{
				x=C[c];
				c++;
				if(C.length()<c)
				{
					cout<<'C'<<endl;
					return 0;
				}
			}
		}
	}
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, n) for (int i = 1; i <= (n); ++i)
#define repd(i, n) for (int i = (n)-1; i >= 0; --i)
#define repds(i, n) for (int i = (n); i > 0; --i)
#define loop(i, x, n) for (int i = (x); i < (n); ++i)
#define loops(i, x, n) for (int i = (x); i <= (n); ++i)
#define loopd(i, x, n) for (int i = (x); i > (n); --i)
#define loopds(i, x, n) for (int i = (x); i >= (n); --i)
#define itrep(i, a) for (auto i = begin(a); i != end(a); ++i)
#define itrepd(i, a) for (auto i = rbegin(a); i != rend(a); ++i)
#define each(i, x) for (auto &&i : x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(a) ((int)a.size())
#define pow2(n) (n * n)
#define int ll
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T>
using priority_queuel = priority_queue<T, vector<T>, greater<T>>;
constexpr ll inf = static_cast<ll>(1e18);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e18;
constexpr double eps = 1e-9;
ll mod = static_cast<ll>(1e9 + 7);
template <class T, class... Args>
constexpr void mins(T &a, Args... args) { a = min<T>({a, args...}); }
template <class T, class... Args>
constexpr void maxs(T &a, Args... args) { a = max<T>({a, args...}); }
template <class F>
class FixPoint : private F {
public:
    explicit constexpr FixPoint(F &&f) : F(std::forward<F>(f)) {}
    template <class... Args>
    constexpr decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, std::forward<Args>(args)...); }
};
template <class F>
constexpr decltype(auto) funcs(F &&f) { return FixPoint<F>{std::forward<F>(f)}; }
template <class T>
std::vector<T> vecs(int n, T &&val) { return std::vector<T>(std::forward<int>(n), std::forward<T>(val)); }
template <class... Args>
decltype(auto) vecs(int n, Args &&... args) { return std::vector<decltype(vecs(std::forward<Args>(args)...))>(std::forward<int>(n), vecs(std::forward<Args>(args)...)); }
template <class V, class T>
void fill(V &x, const T &val) { x = val; }
template <class V, class T>
void fill(vector<V> &vec, const T &val) {
    for (auto &&v : vec)
        fill(v, val);
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> cnt;
    rep(i, n) {
        cin >> a[i];
        ++cnt[a[i]];
    }

    vector<int> used(1000002, bool(false));
    sort(all(a));
    int ans = 0;
    rep(i, n) {
        if (used[a[i]]) continue;
        if (cnt[a[i]] <= 1)
            ++ans;
        for (int j = 1; a[i] * j < 1000002; ++j)
            used[a[i] * j] = true;
    }
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    cout.flush();
    return 0;
}

Measured memory_bytes: 25092
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
// typedef pair<ll, ll> P;
typedef pair<string, int> pa;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main()
{
  int N;
  cin >> N;
  vector<string> S(N);
  vector<int> P(N);
  REP(i, N)
  cin >> S[i] >> P[i];
  pair<pa, int> vc[N];
  REP(i, N)
  vc[i] = make_pair(make_pair(S[i], -1 * P[i]), i + 1);
  sort(vc, vc + N);
  REP(i, N)
  cout << vc[i].second << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] li = new int[n];
        int ans = 0;
        int prev = 0;
        int now = 0;
        for(int i = 0; i < n-1; i++){
            prev = now;
            now = sc.nextInt();
            if(i == 0){
                li[i] = now;
            }else{
                li[i] = Math.min(prev,now);
            }
        }
        li[n-1] = now;
        for(int i : li) ans += i;
        System.out.println(ans);
    }
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define N 131072
#define pi acos(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
int main(){
    char c[20];
    scanf("%s",c);
    int tot=15-strlen(c);
    for(int i=0;c[i]!=0;i++){
        if(c[i]=='o')
            tot++;
    }
    if(tot>=8)
    printf("YES\n");
    else
    printf("NO\n");
}
/*
1 4 2 3
1 3 6 12
k(a+b) = a*b;
k*a+k*b = a*b;
b= (k*a)/(a-k);

k*(k+i)/i
*/

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long en = 100;
        int ans = 0;
        while (x>en) {
            en += en/100;
            ans++;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 35572
#include <bits/stdc++.h>
using namespace std;


void solve(long long N, long long K){
  long long acc = 1;

  for(long long i = 0; i < N; i++){
    if(acc+K < acc*2) {
      acc += K;
    }
    else {
      acc *= 2;
    }
  }

  cout << acc << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
  scanf("%lld",&N);
  long long K;
  scanf("%lld",&K);
    solve(N, K);
    return 0;
}


Measured memory_bytes: 3640
from heapq import heappush, heappop
import sys
from typing import List, Tuple


if __name__ == "__main__":
    V, E, r = map(lambda x: int(x), input().split())

    edges: List[List[Tuple[int, int]]] = [[] for _ in range(V)]
    dists = [sys.maxsize for _ in range(V)]
    dists[r] = 0

    for _ in range(E):
        s, t, dist = map(lambda x: int(x), input().split())
        edges[s].append((t, dist))

    que: List[Tuple[int, int]] = []  # (dist, vertex)
    heappush(que, (0, r))

    while que:
        dist, vertex = heappop(que)
        for to, cost in edges[vertex]:
            if cost + dist < dists[to]:
                dists[to] = cost + dist
                heappush(que, (cost + dist, to))

    for dist in dists:
        if sys.maxsize == dist:
            print("INF")
        else:
            print(dist)



Measured memory_bytes: 91768
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pw(x) (1ll << (x))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i,l,r) for(int i=(l);i<(r);++i)
#define per(i,l,r) for(int i=(r)-1;i>=(l);--i)
#define dd(x) cout << #x << " = " << x << ", "
#define de(x) cout << #x << " = " << x << endl

//-----

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
  string s; cin >> s;
  int ans = 700;
  rep(i, 0, sz(s)) ans += 100 * (s[i] == 'o');
  cout << ans;
	return 0;
}

Measured memory_bytes: 256
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = inp()
if n == 1:
    print(0)
    exit()

f = factorization(n)

ans = 0
for i in range(len(f)):
    sum = f[i][1]
    tmp = 0
    if sum == 1:
        ans += 1
    else:
        for j in range(1,int(sum)):
            tmp += j
            if tmp > sum:
                break
            ans += 1

print(ans)

Measured memory_bytes: 31272
#include <bits/stdc++.h>
using namespace std;

int main() {
int N,T,A ;
    cin >> N >> T >> A ;
int H[N];
  for (int i=0; i<N ; i++){
   cin >> H[i];
  }
int Tem_gap[N];
  for (int i=0; i<N ; i++){
    Tem_gap[i]=1000*T-6*H[i]-1000*A;
    if (Tem_gap[i]<0){
    Tem_gap[i]*=-1 ;
    }
  }

int point=0;
int min_gap =Tem_gap[0];
  for (int i=0; i<N ; i++){
   if (Tem_gap[i]<min_gap){
     min_gap=Tem_gap[i];
   	 point =i;
   }
  }
  
  cout << point+1 << endl;  
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Windows;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Atcoder
{
    public class Program
    {
        static void Main(string[] args)
        {
            var x = Read().Long();
            for (int i = -1000; i < 1000; i++)
            {
                var b = Math.Pow(i, 5);
                for (int j = -1000; j < 1000; j++)
                {
                    if (Math.Pow(j, 5) == x + b)
                    {
                        WriteRead(j.ToString() + " " + i.ToString());
                        return;
                    }
                }
            }
            Read();
        }
        
        public static string Read()
        {
            return Console.ReadLine();
        }

        public static string[] ReadSplit()
        {
            return Console.ReadLine().Split(' ');
        }

        public static void WriteRead(object str)
        {
            Console.WriteLine(str);
            Read();
        }

        public static void Write(object str)
        {
            Console.WriteLine(str);
        }

        private static bool ChangeMin<T>(ref T a, T b) where T : IComparable
        {
            if (a.CompareTo(b) > 0)
            {
                a = b;
                return true;
            }
            return false;
        }

        private static bool ChangekMax<T>(ref T a, T b) where T : IComparable
        {
            if (b.CompareTo(a) > 0)
            {
                a = b;
                return true;
            }
            return false;
        }
    }
}


public static class Extentions
{
    public static int Int(this object obj)
    {
        return int.Parse(obj.ToString());
    }

    public static long Long(this object obj)
    {
        return long.Parse(obj.ToString());
    }

    public static decimal Decimal(this object obj)
    {
        return decimal.Parse(obj.ToString());
    }

    public static double Double(this object obj)
    {
        return double.Parse(obj.ToString());
    }

    public static T2 GetValueZero<T1, T2>(this Dictionary<T1, T2> d, T1 key) where T2 : struct
    {
        T2 value;
        if (d.TryGetValue(key, out value))
        {
            return value;
        }
        return new T2();
    }
}



Measured memory_bytes: 17880
H, W, N = map(int, input().split())
 
Dic = {}
for i in range(N):
    a, b = map(int, input().split())
    for j in range(3):
        for k in range(3):
            if 1 <= a-j <= H-2 and 1 <= b-k <= W-2:
                if (a-j, b-k) in Dic:
                    Dic[(a-j, b-k)] += 1
                else:
                    Dic[(a-j, b-k)] = 1
                    
Painted = [0 for _ in range(10)]
colered = 0

for i in Dic:
    Painted[Dic[i]] += 1
    colered += 1

#最後に黒が一か所も塗られていない場所を、総和-(1ヵ所以上黒)として求める
Painted[0] = (H-2) * (W-2) - colered
 
for i in Painted:
    print(i)

Measured memory_bytes: 166500
#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007

int n;
long long ans;

int main() {
    scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		ans += i * ((long long) n / i) * ((long long) n / i + 1) / 2;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 3788
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int DPSIZE = 370;

struct S {
  int i, j, w;
  bool operator < (const S &s) const {
    return j < s.j;
  }
};

int N;
vector<S> V;
int dp[2][DPSIZE][DPSIZE];

int main() {
  while(cin >> N && N) {
    V.clear();
    for(int i = 0; i < N; ++i) {
      S s;
      cin >> s.i >> s.j >> s.w;
      V.push_back(s);
    }
    sort(V.begin(), V.end());
    fill(dp[0][0], dp[2][0], 0);
    for(int i = 0; i < N; ++i) {
      int p = i % 2;
      int q = 1 - p;
      for(int a = 0; a < DPSIZE; ++a) {
        for(int b = 0; b < DPSIZE; ++b) {
          dp[q][a][b] = dp[p][a][b];
        }
      }
      for(int a = 0; a < DPSIZE; ++a) {
        for(int b = 0; b < DPSIZE; ++b) {
          if(a < V[i].i) {
            dp[q][V[i].j][b] = max(dp[q][V[i].j][b], dp[p][a][b] + V[i].w);
          }
          if(b < V[i].i) {
            dp[q][a][V[i].j] = max(dp[q][a][V[i].j], dp[p][a][b] + V[i].w);
          }
        }
      }
    }
    int res = 0;
    for(int a = 0; a < DPSIZE; ++a) {
      for(int b = 0; b < DPSIZE; ++b) {
        res = max(res, dp[N%2][a][b]);
      }
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 2308
#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

int A, B, C, D, E, F;
double dens = 0.0;
int ans1, ans2;

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    cin >> A >> B;
    cin >> C >> D;
    cin >> E >> F;

    dens = -1.0;
    for(int a = 0; 100 * A * a <= F; a++)
        for(int b = 0; 100 * A * a + 100 * B * b <= F; b++)
        {
            int w = 100 * A * a + 100 * B * b;
            for(int c = 0; w + c * C <= F; c++)
                for(int d = 0; w + c * C + d * D <= F; d++)
                {
                    int s = (c * C + d * D);
                    if(s > (w / 100) * E) break;
                    double dns = (double)(100 * s) / (double)(w + s);
                    if(dns > dens)
                    {
                        dens = dns;
                        ans1 = (w + s);
                        ans2 = s;
                    }
                }
        }
    cout << ans1 << " " << ans2;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "

int main(){
    int n;cin>>n;
    vector<int> a(n),b(n);
    int tmp, sum=0;
    rep(i,n){cin>>tmp;sum+=tmp;a[i]=sum;}
    sum = 0;
    rep(i,n){cin>>tmp;sum+=tmp;b[i]=sum;}
    int mx = a[0]+b[n-1];
    rep1(i,n-1){
        mx = max(mx, a[i]+b[n-1]-b[i-1]);
    }
    co(mx);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int digit(ll n)
{
	int ret=0;
	while(n>0)
	{
		n/=10;
		ret++;
	}
	return ret;
}
int main(){
	ll n;
	cin>>n;
	int res=digit(n);
	for(ll a=1;a*a<=n;a++)
	{
		if(n%a!=0) continue;
		ll b=n/a;
		res=min(res,max(digit(a),digit(b)));
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
using ll=long long;
 
int main()
{
   ll n,x,y;
   vector<pair<ll,ll>>v;
   cin>>n;
   for(int i=0;i<n;i++)
   {
       cin>>x>>y;
       v.push_back({x+y,x});
   }
   sort(v.rbegin(),v.rend());
   ll a=0;
   for(int i=0;i<n;i++)
   {
       if(i%2==0)
        a+=v[i].second;
       else
        a+=v[i].second-v[i].first;
   }
   cout<<a<<endl;
}

Measured memory_bytes: 2420
import sys
import numpy as np


input = sys.stdin.readline

def main():
    N = int(input().rstrip())
    A = np.array(input().rstrip().split(), dtype=np.int64)
    M = 60
    p = 10 ** 9 + 7
    ans = 0

    for m in range(M):
        B = (A >> m) & 1
        x = np.count_nonzero(B)
        x *= N-x
        
        x *= 2 ** m
        x %= p
        ans += x

    print(ans % p)


if __name__ == '__main__':
    main()

Measured memory_bytes: 62760
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int N, K;
    cin>>N>>K;

    vector<int> sequence(N/2, 0);
    sequence.resize(N, 1);

    vector< vector<int> > card(K, vector<int>(N/2));
    for(int i=0; i<K; i++) {
        for(int j=0; j<N/2; j++) {
            cin>>card[i][j];
        }
    }

    while(1) {
        bool ok = true;
        for(int i=0; i<K; i++) {
            int sum = 0;
            for(int j=0; j<N/2; j++) sum += sequence[card[i][j]-1];
            if(sum<N/8 || 3*N/8<sum) ok = false;
        }
        if(ok) break;
        random_shuffle(sequence.begin(), sequence.end());
    }

    for(int i=0; i<N; i++) cout<<sequence[i];
    cout<<endl;
}

Measured memory_bytes: 2060
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <math.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int A, B, K;
    cin >> A >> B >> K;
    vector<int> k;

    for (int i = 1; i <= 100; i++ ) {
      if (A % i == 0 && B % i == 0) {
        k.push_back(i);
      }
    }

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

    cout << k[K-1] << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define maxn 300010
using namespace std;
char s[maxn];
int main()
{
	int n;
	scanf("%d", &n);
	scanf("%s", s + 1);
	int sum_r = 0;
	for (int i = 1; i <= n; i++)
		if (s[i] == 'R') sum_r++;
	int tr = n, now = 0, ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (s[i] == 'R') now++;
		else if (now != sum_r)
		while (true)
		{
			if (s[tr] == 'R')
			{
				now++;
				tr--;
				ans++;
				break;
			}
			tr--;
		}
		if (now == sum_r) break;
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 3904
#include <iostream>
#include <cstdint>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <sstream>
 
int main(void)
{
    int64_t N, K;
    std::cin >> N >> K;

    std::vector<double> expect(10001);
    int64_t sum = 0;
    for (int64_t i = 1; i <= 10000; ++i) {
        sum += i;
        expect.at(i) = (1.0 * sum) / i;
    }

    std::vector<int64_t> dices(N+1);
    for (int64_t i = 1; i <= N; ++i) {
        std::cin >> dices.at(i);
    }

    double max = 0;
    double total = 0;
    for (int64_t i = 1; i <= N; ++i) {
        total += expect.at(dices.at(i));
        if (i < K) continue;
        if (max < total) {
            max = total;
        }
        total -= expect.at(dices.at(i-K+1));
    }

    std::cout << std::fixed;
    std::cout << std::setprecision(10) << max << std::endl;

    return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

long long INF = 1e18;

int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    deque<long long> dp(N, INF);
    for(int i = 0; i < N; i++) {
        long long p = lower_bound(dp.begin(), dp.end(), A[i]) - dp.begin();
        if(p == 0) {
            dp.push_front(A[i]);
        } else {
            dp[p - 1] = A[i];
        }
    }
    cout << lower_bound(dp.begin(), dp.end(), INF) - dp.begin() << endl;
}

Measured memory_bytes: 5608