akhauriyash/Code-Regression huggingface dataset:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main(N, V, W, v, L):
    def precompute(N, V, W):
        U = 10**5 + 10
        dp = np.zeros((1024, U), np.int32)
        for v in range(1, min(1024, N + 1)):
            p = v // 2
            dp[v] = dp[p]
            dp[v, W[v]:] = np.maximum(dp[v, W[v]:], dp[p, :-W[v]] + V[v])
            for i in range(1, U):
                dp[v][i] = max(dp[v][i], dp[v][i - 1])
        return dp

    dp = precompute(N, V, W)
    values = np.empty(1024, np.int32)
    weights = np.empty(1024, np.int32)

    def solve(i, lim, values, weights, dp):
        if i < 1024:
            return dp[i][lim]
        values[0] = 0
        weights[0] = 0
        p = 0
        while i >= 1024:
            for j in range(1 << p):
                values[j + (1 << p)] = values[j] + V[i]
                weights[j + (1 << p)] = weights[j] + W[i]
            p += 1
            i >>= 1
        best = 0
        for n in range(1 << p):
            if weights[n] > lim:
                continue
            x = dp[i][lim - weights[n]] + values[n]
            best = max(best, x)
        return best

    Q = len(v)
    for i in range(Q):
        x = solve(v[i], L[i], values, weights, dp)
        print(x)

        
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i4,i4[:],i4[:],i4[:],i4[:])')(main)
    cc.compile()
    exit()

from my_module import main

N = int(readline())
stdin = np.array(read().split(), np.int32)
V = np.zeros(N + 1, np.int32)
W = np.zeros(N + 1, np.int32)
V[1:] = stdin[:N + N:2]
W[1:] = stdin[1:N + N:2]
query = stdin[N + N + 1:]
v, L = query[::2], query[1::2]

main(N, V, W, v, L)


Measured memory_bytes: 434116
# ワーシャルフロイド法
n,w = map(int,input().split()) #n:頂点数　w:辺の数

d = [[float("inf") for i in range(n)] for i in range(n)] 

# 入力の辺リスト
e_list = []
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
    # 入力の辺リストに追加
    e_list.append([x-1,y-1,z])
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
    
#d[i][j]: iからjへの最短距離
for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])

# 移動コスト表示
#print(d)
##############################

# 辺の数から使用済みの数を引く
ans = w
for x, y, z in e_list:
    # dにx,y,z の情報が残っていたら利用されている
    if d[x][y] == z:
        ans -= 1
        
print(ans)

Measured memory_bytes: 46700
#include "bits/stdc++.h"
using namespace std;

int main(){
  int H,W,K; cin >> H >> W >> K;
  
  vector<string> c(H);
  for (int i = 0; i < H; i++) cin >> c.at(i);
  //for (int i = 0; i < H; i++) cout << c.at(i) << endl;
  int bt = 0;
  int ans = 0;
  while (bt < (1 << (H+W))){
    vector<bool> H_bool(H,false),W_bool(W,false);
    for (int k = 0; k < H+W; k++) {
	  if ((bt >> k) & 1){
        if (k > H-1) W_bool[k-H] = true;
        else H_bool[k] = true;
      }
    }
    int counter = 0;
    for (int i = 0; i < H; i++){
      for (int j = 0; j < W; j++){
        if (c[i][j] == '#' && H_bool[i] == false && W_bool[j] == false) counter++;
      }
    }
    if (counter == K) ans++;
    bt++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3624
# coding: utf-8

def getMin(X, K):
    minVal = float('inf')
    for l in range(len(X)-K+1):        
        minVal = min(minVal, abs(X[l]) + abs(X[K + l - 1] - X[l]))
        minVal = min(minVal, abs(X[K + l - 1]) + abs(X[l] - X[K + l - 1]))
    return minVal

if __name__ == "__main__":
    N, K = map(int, input().split())
    X = list(map(int, input().split()))
    print(getMin(X, K))



Measured memory_bytes: 14380
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include <sstream>
#include<map>


using namespace std;

map<string, int> mapToInt =
{
	{ "01", 1 },
	{ "02", 2 },
	{ "03", 3 },
	{ "04", 4 },
	{ "05", 5 },
	{ "06", 6 },
	{ "07", 7 },
	{ "08", 8 },
	{ "09", 9 },
};

int ConvStrToInt(std::string checkStr)
{
	if (mapToInt.count(checkStr) != 0)
	{
		return mapToInt[checkStr];
	}
	return atoi(checkStr.c_str());
}

int ConvStrToInt(char c)
{
	if ('0' <= c && c <= '9') return (c - '0');
	return -1;
}

int main() {

	string S;
	cin >> S;

	string LEFT = S.substr(0, 2);
	string RIGHT = S.substr(2, 2);

	int left = ConvStrToInt(LEFT);
	int right = ConvStrToInt(RIGHT);

	string result = "";
	if (1 <= left && left <= 12)
	{
		// 月 or 年
		if (1 <= right && right <= 12)
		{
			// 年/月 or 月/年
			result = "AMBIGUOUS";
		}
		else
		{
			// 月/年
			result = "MMYY";
		}
	}
	else
	{
		// 年?
		if (1 <= right && right <= 12)
		{
			// 年/月
			result = "YYMM";
		}
		else
		{
			// あり得ない
			result = "NA";
		}
	}

	cout << result << endl;

	return 0;
}




Measured memory_bytes: 256
import bisect

n = 10**5
primes = set(range(2, n+1))
for i in range(2, int(n**0.5)+1):
    primes.difference_update(range(i*2, n+1, i))
primes = list(primes)

l_2017 = []
for p in primes[1:]:
    if (p+1)//2 in primes:
        l_2017.append(p)

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(bisect.bisect_right(l_2017, r) - bisect.bisect_left(l_2017, l))


Measured memory_bytes: 65380
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int a,b,c,k;
   cin >> a >> b >> c >> k;
   if(k<=a+b){
      cout << min(k,a) << '\n';
      return 0;
   }
   int ans = a;
   int rem = k-(a+b);
   ans -= rem;
   cout << ans << '\n';
   return 0;
}

Measured memory_bytes: 3640
// Contest: AtCoder Beginner Contest 158 (https://atcoder.jp/contests/abc158)
// Problem: D: String Formation (https://atcoder.jp/contests/abc158/tasks/abc158_d)


// region {{{ boilerplate
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <chrono>
#include <cstdint>
#include <deque>
#include <exception>
#include <forward_list>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#if __cplusplus >= 201703L
#   include <optional>
#   include <string_view>
#   include <variant>
#endif

using namespace std;

#if __cplusplus >= 201703L
#   define all(a)      begin(a),end(a)
#   define sz(x)       ((int)size(x))
#else
#   define all(a)      (a).begin(),(a).end()
#   define sz(x)       ((int)(x).size())
#endif

#define rep(a, b)      for(int a = 0; a < (b); ++a)
#define reps(a, b, c)  for(int a = (b); a < (c); ++a)
#define trav(a, b)     for(auto& a : b)

using ll = long long;
using ld = long double;
using u64 = uint64_t;
using u32 = uint32_t;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vpi = vector<pi>;

#if __cplusplus >= 201703L
#   define MAYBE_UNUSED [[maybe_unused]]
#else
#   define MAYBE_UNUSED
#endif

MAYBE_UNUSED static constexpr int INF = (int)1e9 + 5;
MAYBE_UNUSED static constexpr ll INFL = (ll)1e18 + 5;
MAYBE_UNUSED static mt19937 rng((u32)chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
//endregion }}}

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

    string si; cin >> si;
    deque<char> s(all(si));

    bool rev = false;
    int q; cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1)
            rev = !rev;
        else {
            int f; char c; cin >> f >> c;
            if ((f == 2) == rev)
                s.push_front(c);
            else
                s.push_back(c);
        }
    }
    if (rev)
        reverse(all(s));
    trav(c, s)
        cout << c;
    cout << '\n';

    return 0;
}

Measured memory_bytes: 976
import sys
from collections import deque
import itertools


def input():
    return sys.stdin.readline().rstrip()


def main():
    x,y = map(int,input().split())
    if (x+y)%3 !=0:
        print(0)
        exit()
    if x*2 <y or y *2 <x:
        print(0)
        exit()

    n = int((x+y)/3)
    #conbination y-n from N or  x-n from N


    mod = 10 ** 9 + 7  # 出力の制限
    N = 10 ** 6
    g1 = [1, 1]  # 元テーブル
    g2 = [1, 1]  # 逆元テーブル
    inverse = [0, 1]  # 逆元テーブル計算用テーブル

    def cmb(n, r, mod):
        if (r < 0 or r > n):
            return 0
        r = min(r, n - r)
        return g1[n] * g2[r] * g2[n - r] % mod
    for i in range(2, N + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    a = cmb(n, x-n, mod)

    print(a)
if __name__ == "__main__":
    main()


Measured memory_bytes: 215680
s=input()
s1=""
s2=""
count_1=0
l=[]
num =int(input())
 
 
for x in range(num):
    i=input().rstrip().split()
    if i[0]=="1":
        count_1+=1
        
    elif i[1]=="1" and count_1%2==0:
        s1=i[2]+s1
   
    elif i[1]=="1" and count_1%2==1:
        s2=s2+i[2]
 
    elif i[1]=="2" and count_1%2==0:
        s2=s2+i[2]
 
    elif i[1]=="2" and count_1%2==1:
        s1=i[2]+s1
s=s1+s+s2
 
if count_1%2==1:
    s=s[::-1]
print(s)

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

int main() {
  long A, B, C;
  cin >> A >> B >> C;
  if (A % 2 == 0 || B % 2 == 0 || C % 2 == 0) {
    cout << 0 << endl;
    return 0;
  }
  vector<long> ar = {A, B, C};
  sort(ar.begin(), ar.end());
  long ans = ar[0] * ar[1];
  cout << ans << endl;
}

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

using namespace std;

int main() {

	long long n;
	cin >> n;

	long long a, b, c, ans, bns, cns;
	for (long i = 0; i < n; i++) {
		cin >> a >> b >> c;
		if (i == 0) {
			ans = a, bns = b, cns = c;
		} else {

			long long newans = ans, newbns = bns, newcns = cns;
			ans = max(newbns, newcns) + a;
			bns = max(newcns, newans) + b;
			cns = max(newans, newbns) + c;
		}

	}

	cout << max(ans , max(bns  , cns )) << endl;
	return 0;

}


Measured memory_bytes: 3604
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <complex>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
#include <iterator>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

int main() {
    double r;
    cin >> r;
    printf("%.10f\n", r * 6.283185307179586232);
    return 0;
}

Measured memory_bytes: 3788
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200000 + 5;

char col[maxn];
int dp[maxn][2], n;

int main() {	
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    cin >> col + 1;
    int cnt = 0;
    int l = 1, r = n;
    while(l < r) {
        while(col[l] == 'R') l++;
        while(col[r] == 'W') r--;
        if(l < r) 
          cnt++, swap(col[l], col[r]);
    }
    cout << cnt;
    return 0;
}

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

#define fi first
#define se second
#define ll long long

const int N = 20010;
const long long mod = 1e9 + 7;

using namespace std;

int n;
int a[N];
int b[N];
int c[N];
long long d[N];

bool cmp(int x, int y)
{
        return a[x] + b[x] < a[y] + b[y];
}

int main()
{
        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
        ios_base::sync_with_stdio(0);

        cin >> n;
        vector < int > v;
        for(int i = 1; i <= n; i++){
                cin >> a[i] >> b[i] >> c[i];
                v.push_back(i);
        }
        sort(v.begin(), v.end(), cmp);
        for(int i: v){
                for(int j = b[i]; j >= 0; j--){
                        d[j + a[i]] = max(d[j + a[i]], d[j] + c[i]);
                }
        }
        long long res = 0;
        for(int i = 1; i < N; i++){
                res = max(res, d[i]);
        }
        cout << res << "\n";
}


Measured memory_bytes: 512
while True:
    
    n,k = map(int,input().split())
    if n==0 and k==0:
        break

    a = [int(input()) for i in range(n)]
    b = 0
    s = [0]*(n+1)
    
    for i in range(n):
        s[i+1]=s[i]+a[i]
        
    for i in range(n-k+1):
        tmp = s[k+i]-s[i]
        if tmp>b:
            b = tmp

    print(b)


Measured memory_bytes: 13420
#include<iostream>
using namespace std;
int sx,sy,ex,ey;

int step;
int w,h;
void rec(int stage[21][21],int x,int y,int d){
  int bx,by;
  if(d>=step) return;
  //cout << d << endl;
  int st[21][21];
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      st[j][i]=stage[j][i];

  //right
  bx=x;by=y;
  while(bx<w-1&&stage[bx+1][by]==0) bx++;
  if(bx+1==w){
    //rec(stage,bx,by,d+1);
  }else if(stage[bx+1][by]==3){
    step=min(step,d+1);
    st[bx][by]=2;
    /*
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cout << st[j][i] << " ";
      }
      cout << endl;
    }
    */
  }else if(stage[bx+1][by]==1){
    if(bx!=x||by!=y){
      st[bx+1][by]=0;
      rec(st,bx,by,d+1);
      st[bx+1][by]=1;
    }
  }
  
  //left
  bx=x;by=y;
  
  while(bx>0&&stage[bx-1][by]==0) bx--;
  if(bx==0){
    //rec(st,bx,by,d+1);
  }else if(stage[bx-1][by]==3){
    step=min(step,d+1);
  }else if(stage[bx-1][by]==1){
    if(bx!=x||by!=y){
      st[bx-1][by]=0;
      rec(st,bx,by,d+1);
      st[bx-1][by]=1;
    }
  }
  //up
  bx=x;by=y;
  
  while(by<h-1&&stage[bx][by+1]==0) by++;
  if(by+1==h){
    //rec(st,bx,by,d+1);
  }else if(stage[bx][by+1]==3){
    step=min(step,d+1);
  }else if(stage[bx][by+1]==1){
    if(bx!=x||by!=y){
      st[bx][by+1]=0;
      rec(st,bx,by,d+1);
      st[bx][by+1]=1;
    }
  }
  //down
  bx=x;by=y;
  
  while(by>0&&stage[bx][by-1]==0) by--;
  if(by==0){
    //rec(st,bx,by,d+1);
  }else if(stage[bx][by-1]==3){
    step=min(step,d+1);
  }else if(stage[bx][by-1]==1){
    if(bx!=x||by!=y){
      st[bx][by-1]=0;
      rec(st,bx,by,d+1);
      st[bx][by-1]=1;
    }
  }
}
int main(){
  cin >> w >> h;
  while(w!=0){
    int stage[21][21]={{}};
    int b;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cin >> stage[j][i];
	if(stage[j][i]==2) {
	  stage[j][i]=0;
	  sx=j;
	  sy=i;
	}
      }
    }
    step=11;
    rec(stage,sx,sy,0);
    if(step>10) cout << -1 << endl;
    else cout << step << endl;
    cin >> w >> h;
  }
  return 0;
}

Measured memory_bytes: 1180
#include <bits/stdc++.h>
#define N 110
using namespace std;
typedef pair<int,int> P;
typedef pair<P,P> PP;
int n,Dis[N],Dir[N],mp[N][N];
int dx[]={0,2,0,-2};
int dy[]={2,0,-2,0};

bool checkDir(int y,int x,int dir,int ndir){
  int nx = x+dx[ndir]/2;
  int ny = y+dy[ndir]/2;
  return !((dir+2)%4==ndir||nx<0||ny<0||mp[ny][nx]==0);
}

int used[N][N][4];
set<PP> mem[N][N][4][12];
set<PP> getNx(int sy,int sx,int sdir,int d){
  if(used[sy][sx][sdir]++) return mem[sy][sx][sdir][d];
  bool D[N][N][4][12]={};
  queue<PP> Q;
  
  int nsy = 2*sy + dy[sdir];
  int nsx = 2*sx + dx[sdir];
  if(!checkDir(2*sy,2*sx,sdir,sdir)) return set<PP>();
  D[nsy][nsx][sdir][1] = 1;
  Q.push(PP(P(nsy,nsx),P(sdir,1)));
  mem[sy][sx][sdir][1].insert(PP(P(nsy/2,nsx/2),P(sdir,-1)));
  
  while(!Q.empty()){
    PP t = Q.front();Q.pop();
    int y = t.first.first;
    int x = t.first.second;
    int dir = t.second.first;
    int c = t.second.second;
    
    if(c==10)continue;
    for(int i=0;i<4;i++){
      int nx = x+dx[i];
      int ny = y+dy[i];
      if(!checkDir(y,x,dir,i)||D[ny][nx][i][c+1])continue; 
      D[ny][nx][i][c+1] = 1;
      Q.push(PP(P(ny,nx),P(i,c+1)));
      mem[sy][sx][sdir][c+1].insert(PP(P(ny/2,nx/2),P(i,-1)));
    }    
  }
  return mem[sy][sx][sdir][d];
}

set<P> bfs(int sy,int sx){
  set<P> res;
  bool D[N][N][N][4]={};
  queue<PP> Q;
  
  for(int i=0;i<4;i++)D[0][sy][sx][i] = 1,Q.push(PP(P(0,sy),P(sx,i)));
  
  while(!Q.empty()){
    PP t = Q.front();Q.pop();
    int idx = t.first.first;
    int y = t.first.second;
    int x = t.second.first;
    int dir = t.second.second;
    if(idx==n) {res.insert(P(x,y));continue;}

    set<PP> R = getNx(y,x,dir,Dis[idx]);
    for(PP r:R){
      int ny = r.first.first;
      int nx = r.first.second;
      int rdir = r.second.first;
      int ndir = Dir[idx];
      
      if(ndir == rdir)
	for(int j=0;j<4;j++){
	  if(!checkDir(2*ny,2*nx,rdir,j)||D[idx+1][ny][nx][j]) continue;
	  D[idx+1][ny][nx][j] = 1;
	  Q.push(PP(P(idx+1,ny),P(nx,j)));
	}

      if(ndir==rdir||!checkDir(2*ny,2*nx,rdir,ndir)||D[idx+1][ny][nx][ndir]) continue;
      D[idx+1][ny][nx][ndir] = 1;
      Q.push(PP(P(idx+1,ny),P(nx,ndir)));
    } 
  }
  return res;
}

int main(){
  int m,sx,sy;
  cin>>m>>sx>>sy>>n;
  
  for(int i=0,x,y,X,Y;i<m;i++){
    cin>>x>>y>>X>>Y;
    if(x>X)swap(x,X);
    if(y>Y)swap(y,Y);
    for(int i=2*y;i<=2*Y;i++)
      for(int j=2*x;j<=2*X;j++) mp[i][j] = 1;
  }

  for(int i=0;i<n;i++){
    char ch;
    cin>>Dis[i]>>ch;
    if(ch == 'N') Dir[i] = 0;
    if(ch == 'E') Dir[i] = 1;
    if(ch == 'S') Dir[i] = 2;
    if(ch == 'W') Dir[i] = 3;
  }

  set<P> ans = bfs(sy,sx);
  for(P a:ans)cout<<a.first<<" "<<a.second<<endl;
  return 0;
}

Measured memory_bytes: 166780
#include <stdio.h>
#include <algorithm>
int n, k, x, y;
int a[200000];
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", a + i);
		a[i]++;
	}
	for (int i = 0; i < k; i++) {
		x += a[i];
		y = x;
	}
	for (int i = k; i < n; i++) {
		x -= a[i - k];
		x += a[i];
		if (x > y)y = x;
	}
	printf("%d", y / 2);
	if (y % 2)printf(".5");
	printf("\n");
}

Measured memory_bytes: 896
import scala.io.StdIn.{readInt, readLine}

object Main extends App {

  val n = readInt
  val arr = readLine.split(" ").map(_.toInt)
  println(findNoOfInversion(arr))

  def findNoOfInversion(arr: Array[Int]): Long = {
    mergeSort(arr, 0, arr.length - 1, 0)
  }

  def mergeSort(arr: Array[Int], left: Int, right: Int, cnt: Long): Long = {
    if (left == right) {
      return 0
    }
    val mid = (left + right) / 2
    var count = cnt
    count += mergeSort(arr, left, mid, cnt)
    count += mergeSort(arr, mid + 1, right, cnt)
    count += merge(arr, left, mid, right, cnt)
    count
  }

  def merge(arr: Array[Int], left: Int, mid: Int, right: Int, cnt: Long): Long = {
    val len1 = mid + 1 - left
    val len2 = right - mid
    val L: Array[Int] = Array.fill[Int](len1 + 1)(0)
    val R: Array[Int] = Array.fill[Int](len2 + 1)(0)
    for (i <- 0 until len1) L(i) = arr(left + i)
    for (i <- 0 until len2) R(i) = arr(mid + 1 + i)
    L(len1) = Integer.MAX_VALUE
    R(len2) = Integer.MAX_VALUE
    var count = cnt
    var i = 0
    var j = 0
    var k = left
    while (k <= right) {
      if (L(i) < R(j)) {
        arr(k) = L(i)
        i += 1
      } else {
        arr(k) = R(j)
        count += (j + mid + 1) - k
        j += 1
      }
      k += 1
    }
    count
  }
}



Measured memory_bytes: 133696
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
int a[SIZE];
int main(){
    DRIII(N,C,K);
    REP(i,N)RI(a[i]);
    sort(a,a+N);
    int an=0;
    for(int i=0,j;i<N;i=j){
        an++;
        for(j=i+1;j<N&&j-i<C&&a[j]-a[i]<=K;j++);
    }
    printf("%d\n",an);
    return 0;
}


Measured memory_bytes: 640
fun main(args: Array<String>) = ABC163B.main()

object ABC163B {
    fun main() {
        val (N, M) = readInts()
        val A = readInts()
        val remain = N - A.sum()
        val ans = if (remain >= 0) remain else -1
        println(ans)
    }


    /*####################################################################################*/

    fun readString() = readLine()!!
    fun readStrings() = readLine()!!.split(" ")
    fun readInt() = readLine()!!.toInt()
    fun readInts() = readLine()!!.split(" ").map { it.toInt() }
    fun readMatrixRows(height: Int) = (1..height).map { readLine()!!.toList() }

    fun Boolean.yesOrNo() = if (this) "Yes" else "No"
    fun Double.toNaturalExpr() = println("%f".format(this))
}

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

int f(int n) {
    int ans = 0;
    while (n) {
        ans += n%10;
        n/=10;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    int n, a, b, ans = 0;
    cin >> n;
    if (n % f(n) == 0)
        cout << "Yes";
    else
        cout << "No";

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;



int main(){
    ll n; cin >> n;
    cout << n*(n-1)/2 << endl;
}


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

int main() {
  
  int W,H,N;
  cin >> W >> H >> N;
  
  vector<vector<int>> A(W, vector<int>(H,0));
  
  int x,y,a;
  for(int i=0; i<N; i++){
    cin >> x >> y >> a;
    
    if(a==1){
      for(int j=0; j<x; j++){
        for(int k=0; k<H; k++){
          A.at(j).at(k) = 1;
        }
      }
    }
    
    else if(a==2){
      for(int j=x; j<W; j++){
        for(int k=0; k<H; k++){
          A.at(j).at(k) = 1;
        }
      }
    }
    
    else if(a==3){
      for(int j=0; j<W; j++){
        for(int k=0; k<y; k++){
          A.at(j).at(k) = 1;
        }
      }
    }
    
    else if(a==4){
      for(int j=0; j<W; j++){
        for(int k=y; k<H; k++){
          A.at(j).at(k) = 1;
        }
      }
    }
    
  }
  
  int ans=0;
  for(int i=0; i<W; i++){
    for(int j=0; j<H; j++){
      if(A.at(i).at(j) == 0){
        ans++;
      }
    }
  }
   
  cout << ans << endl;
  
}


Measured memory_bytes: 3592
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;

int main()
{
    ll k, x, y;
    cin>>k>>x>>y;
    ll d=abs(x)+abs(y);
    if(k%2==0 && d%2==1){
        cout<<-1<<endl;
        return 0;
    }
    if(d==k){
        cout<<1<<endl;
        cout<<x<<" "<<y<<endl;
        return 0;
    }
    ll p=1, q=1;
    if(x<0) p=-1;
    if(y<0) q=-1;
    x=abs(x), y=abs(y);
    vector<P> v;
    ll x0=0, y0=0;
    while(x0+y0<d-2*k){
        v.push_back({x0, y0});
        if(x>=x0+k) x0+=k;
        else if(y>=y0+k) y0+=k;
    }
    v.push_back({x0, y0});
    ll x1=x-x0, y1=y-y0;
    if(k%2==1 && (x1+y1)%2==1){
        if(x1>=k) x0+=k;
        else y0+=k;
        v.push_back({x0, y0});
        x1=x-x0, y1=y-y0;
    }
    ll r=1, s=1;
    if(x1<0) r=-1;
    if(y1<0) s=-1;
    x1=abs(x1), y1=abs(y1);
    ll t=(x1-y1)/2;
    if(x1>=y1) v.push_back({x0+r*t, y0+s*(k-t)});
    else v.push_back({x0+r*(k+t), y0-s*t});
    v.push_back({x, y});
    cout<<v.size()-1<<endl;
    for(int i=1; i<v.size(); i++) cout<<v[i].first*p<<" "<<v[i].second*q<<endl;
    return 0;
}

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

vector<int> make()
{
	bool b[50001] = {};
	for(int i = 2; i*i < 50001; ++i){
		if(!b[i]){
			for(int j = i*i; j < 50001; j += i){
				b[j] = true;
			}
		}
	}
	vector<int> prime;
	prime.reserve(50000);
	for(int i = 2; i < 50001; ++i){
		if(!b[i]){
			prime.push_back(i);
		}
	}

	return prime;
}
	

int main()
{
	int n;
	vector<int> prime = make();
	while(cin >> n, n){
		int ans = 0;
		for(int i = 0; i < (int)prime.size(); ++i){
			if(prime[i] > n) break;
			if(binary_search(prime.begin() + i, prime.end(), n - prime[i])){
				ans++;
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1240
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
public class MainClass
{
	public const long Giri = 1000000007;
	public const long DpInf = 99999999999999;
	
	public static void Main(string[] args)
	{
		var n = Console.ReadLine().ToInt();
		var q = Input();
		var a = new long[n];
		long allxor = 0;
		for(int i = 0; i < n; i++)
		{
			a[i] = q[i].ToLong();
			allxor ^= a[i];
		}
		for(int i = 0; i < n; i++)
		{
			allxor ^= a[i];
			Console.Write("{0} ", allxor );
			allxor ^= a[i];
			
		}
		Console.WriteLine();

	}

	
	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str, int offset = 0)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt() + offset;
		return r;
	}
}

Measured memory_bytes: 51208
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,int> pii;

int square(int x) {
  return x*x;
}

bool cmp(const pii &a, const pii &b) {
  const int sqa = square(a.first)+square(a.second);
  const int sqb = square(b.first)+square(b.second);
  if (sqa != sqb) return (sqa < sqb);
  return (a.first < b.first);
}

int main() {
  vector<pii> memo;
  for (int i=0;i<150;i++) {
    for (int j=0;j<i;j++) {
      memo.push_back(pii(j+1, i+1));
    }
  }
  sort(memo.begin(), memo.end(), cmp);
  while (true) {
    int h, w;
    scanf("%d %d", &h, &w);
    if (h == 0 && w == 0) break;
    vector<pii>::iterator p = find(memo.begin(), memo.end(), pii(h, w))+1;
    printf("%d %d\n", p->first, p->second);
  }
  return 0;
}

Measured memory_bytes: 2848
#include <stdio.h>
int main()
{
	int N, flag = 0;
	scanf("%d", &N);
	for(int i=1;i<=N;i++)
	{
		double t = i*1.08;
		if((int)t==N)
		{
			printf("%d\n", i);
			return 0;
		}
		if((int)t>N)
		{
			printf(":(\n");
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 128
import string
from collections import deque

deq = deque(string.ascii_uppercase)
lis = list(string.ascii_uppercase)

#INPUTS
N = int(input())
str_ = list(input())
deq.rotate(-N) 

mem = list()
for s in str_:
  i = lis.index(s)
  mem.append(deq[i])
  
print("".join(mem))


Measured memory_bytes: 3828
M = 1000000007
N = int(input())
left = list(map(int, input().split()))


def solve():
    res = 1
    h = [0, 0, 0]
    for i in range(N):
        k = h.count(left[i])
        res = res * k % M
        for j in range(3):
            if h[j] == left[i]:
                h[j] += 1
                break
    return res


print(solve())


Measured memory_bytes: 13964
#include <stdio.h>

int judge(int *, int);

int n;

int main(){
  int q, S[100000], T[50000];
  int i, cnt = 0;


  scanf("%d", &n);

  for(i= 0; i < n; i++){
    scanf("%d", &S[i]);
  }

  scanf("%d", &q);

  for(i = 0; i < q; i++){
    scanf("%d", &T[i]);
  }

  for(i = 0; i < q; i++){
    cnt += judge(S, T[i]);
  }

  printf("%d\n", cnt);

  return 0;
}


int judge(int *A, int key){
  int  left, right, mid;

  left = 0;
  right = n;

  while(left < right){
    mid = (left + right) / 2;

    if(A[mid] == key)     return 1;

    else if(key < A[mid]) right = mid;

    else                  left = mid + 1;
  }

  return 0;
}



Measured memory_bytes: 2356
#include <iostream>
using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if(a==b && a!=c)
    {
        cout << "Yes";
    }
    else if(a!=b && a==c)
        cout << "Yes";
    else if(b==c && a!=b)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}


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

using namespace std;

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cout << setprecision(9) << fixed;

    int n, k;
    cin >> n >> k;

    double total = 0;
    for(int i=1;i<=n;++i){
        if(i >= k) total += 1.0/n;
        else{
            int t = 0;
            while((i << t) < k) t++;
            total += 1.0/n * pow(0.5, t);
        }
    }

    cout << total << '\n';

    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include<vector>
#include<algorithm>
#include <queue>
#include <string>
#include <set>
#include <bitset>

using namespace std;
#define ff(ii,nn,mm) for(int ii=nn;ii<mm;ii++)
#define i64 int64_t
#define tos(x) to_string(x)


int main() {
	int b = 0;
	vector<vector<int>> a = { {1,3,5,7,8,10,12},{4,6,9,11},{2} };
	int x, y;
	cin >> x >> y;
	ff(i, 0, 3) {
		b = 0;
		ff(j, 0, a.at(i).size()) {
			if (a.at(i).at(j) == x) b++;
			if (a.at(i).at(j) == y)b++;
		}
		if (b == 2) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
class Program
    {
    	static void Main(string[] args)
    	{
    		// 整数の入力
    		int a = int.Parse(Console.ReadLine());
    		// 数列の入力
            string[] s = new string[a];
    		for (int i = 0; i < a; i++)
            {
                s[i] = Console.ReadLine();
            }
    		//出力
            int ans = 0;
            for (int i = 0; i < a; i++)
            {
                bool goodPattern = true;
                for (int j = 0; j < a; j++)
                {
                    for (int k = 0; k < a; k++)
                    {
                        if (s[(j + i) % a][k] != s[(k + i) % a][j])
                        {
                            goodPattern = false;
                            break;
                        }
                    }
                    if (goodPattern == false) break;
                }
                if (goodPattern) ans += a;
            }
            Console.WriteLine(ans);
        }
    }
    //mcs Main.cs
    //mono Main.exe

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

int a[2], k;

int main()
{
	scanf("%d%d%d", &a[0], &a[1], &k);
	for (int i=0; i<k; i++)
	{
		int tmp = a[i%2]>>1;
		a[i%2] >>= 1;
		a[1-(i%2)] += tmp;
	}
	printf("%d %d\n", a[0], a[1]); 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,h) for(int i = 0; i < h; ++i)
#define rep1(i,h) for(int i = 0; i <= h; ++i)
#define rep2(i,n,h) for(int i = n; i < h; ++i)
#define rep3(l,n,h) for(int l = n; l <= h; ++l)
typedef pair<int,int> int_pair;
typedef pair<string,string> string_pair;


int main(void) {
    int  a,b,c;
    cin >> a >> b>> c;
    if(a+b+c >= 22) {
        cout << "bust";
    }else {
        cout << "win";
    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i=s;i<n;i++)
#define pb push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using P=pair<int,int>;
using G=vector<vector<int>>;
using ll=long long;


#define pi 3.141592653589793

vector<pair<int64_t,int64_t>> soinsuu(int64_t n){
    vector<pair<int64_t,int64_t>> ret;
    for(int64_t i=2;i*i<=n;i++){
        if(n%i !=0) continue;
        int64_t ex=0;
        while(n%i ==0){
            ex++;
            n /= i; //n変更することで、それ以降の約数で割り切れることはない
        }
        ret.push_back(make_pair(i,ex));
    }
    //nが素数だった場合
    if(n!=1) ret.push_back(make_pair(n,1));
    return ret;
}

int n,m,q;
vector<int> a,b,c,d;
int ans;

void dfs(vector<int> A){
  if(A.size()==n+1){
    int now=0;
    rep(i,0,q){
      if(A[b[i]]-A[a[i]]==c[i]) now+=d[i];
    }
    ans=max(ans,now);
    return;
  }

  A.push_back(A.back());
  while(A.back()<=m){
    dfs(A);
    A.back()++;
  }

}
int main(int argc,char **argv){
  cin>>n>>m>>q;
  a=b=c=d=vector<int>(q);
  rep(i,0,q){
    cin>>a[i]>>b[i]>>c[i]>>d[i];
  }

  dfs(vector<int>(1,1));
  cout<<ans<<endl;
  return 0;
  }

Measured memory_bytes: 3556
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus >= 201703L
#        pragma GCC target("avx2")
#    else
#        pragma GCC target("avx")
#    endif

#endif
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    int c[4][4] = {};
    for (int i = 1; i < 4; i++) {
        for (int k = 1; k < 4; k++) {
            cin >> c[i][k];
        }
    }

    bool ans = true;
    for (int i = 1; i <= 3; i++) {
        for (int j = i + 1; j <= 3; j++) {
            int tem = c[j][1] - c[i][1];
            for (int k = 2; k <= 3; k++) {
                if (tem != c[j][k] - c[i][k]) {
                    ans = false;
                }
            }
        }
    }
    for (int i = 1; i <= 3; i++) {
        for (int j = i + 1; j <= 3; j++) {
            int tem = c[1][j] - c[1][i];
            for (int k = 2; k <= 3; k++) {
                if (tem != c[k][j] - c[k][i]) {
                    ans = false;
                }
            }
        }
    }

    if (ans) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long 
using namespace std;




int main() {
   #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 ll n; cin>>n; 
 vector<ll>v(n);
 ll sum=0;
 for(int i=0;i<n;i++) {
  cin>>v[i]; sum+=v[i];
 }
 ll m; cin>>m; 
 while(m--){
  ll a,b; cin>>a>>b;
  cout<<sum-v[a-1]+b<<endl;
 }
  return 0;
}


Measured memory_bytes: 3616
import java.util.*;
import java.io.*;

class Main{
  public static void main(String[] args){
   	Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int s;

    if((a + b) % 2 == 0){
      s = (a + b)/2;
      System.out.println(s);
    }else{
      System.out.println("IMPOSSIBLE");
    }

    }

  }


Measured memory_bytes: 21844
#include <iostream>
using namespace std;
int main(void){
  int a, b, c, x;
  cin >> a >> b >> c;
  x = a * 100 + b * 10 + c;
  if(x % 4 == 0)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  
  return 0;
}

Measured memory_bytes: 256
from itertools import permutations

N = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

R = [i for i in range(1, N+1)]

li = []
for i in permutations(R, N):
    li.append(list(i))

print(abs(li.index(P) - li.index(Q)))

Measured memory_bytes: 10228
#include <bits/stdc++.h>
#ifdef __DEBUG__
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const deque<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const set<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

// long double a;
// long double b;
ll a;
string b;
int B = 0;
void input(){
    fast_io();
    cin >> a >> b;
    for (int i = 0; i < b.length(); i++)
    {
        if(b[i]>='0' && b[i]<='9'){
            B *= 10;
            B += (b[i]-'0');
        }
    }
    
}

// int Tsolve(){
//     long double ans = a*b;
//     cout << (ll)ans << endl;
//     return 0;
// }   

int solve(){
    DBG(b)
    DBG(B)
    ll ans = (a*B)/100;
    cout << ans << endl;
    return 0;
}

int main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 3596
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
	int ans;
	long long x,y;
    cin>>x>>y;
    long long i=x;
    while(i<=y) ++ans,i*=2;
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  const int N = 100100;
  vector<bool> isp(N, true);
  isp[0] = isp[1] = false;
  for (int i = 2; i * i < N; i++) {
    if (isp[i]) {
      for (int j = i * i; j < N; j += i) {
        isp[j] = false;
      }
    }
  }
  vector<int> sum(N, 0);
  for (int i = 3; i < N; i++) {
    sum[i] += sum[i - 1] + (isp[i] && isp[(i + 1) / 2]);
  }
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    cout << sum[r] - sum[l - 1] << endl;
  }
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define N 200005
int seg[4*N];

void update(int st, int l, int r, int idx, int val)
{
    if(l == r)
    {
        seg[st] = val;
        return;
    }
    int mid = (l+r)/2;
    if(idx <= mid)
        update(2*st+1, l, mid, idx, val);
    else
        update(2*st+2,mid+1, r, idx, val);
    seg[st] = max(seg[2*st+1],seg[2*st+2]);    
}
int query(int st, int l, int r, int ql, int qr)
{
    if(l > qr || r < ql)
    {
        return 0;
    }
    if(l >= ql && r <= qr)
        return seg[st];
    int mid = (l+r)/2;
    return max(query(2*st+1, l, mid, ql, qr), query(2*st+2, mid+1, r, ql, qr));
}
signed main() {
    int n;
    cin >> n;
    int h[n], a[n];
    int i;
    for(i=0;i<n;i++)
    {
        cin >> h[i];
        h[i]--;
    }
    for(i=0;i<n;i++)
        cin >> a[i];
    int dp[n];
    dp[0] = a[0];
    update(0, 0, n-1, h[0], dp[0]);
    for(i=1;i<n;i++)
    {
        int mx = query(0, 0, n-1, 0, h[i]);
        dp[i] = a[i] + mx;
        update(0, 0, n-1, h[i], dp[i]);
    }
    cout << *max_element(dp, dp+n);
}

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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  vector<int> vec = {a, b, c};
  sort(vec.begin(), vec.end());

  if (vec.at(0) + vec.at(1) == vec.at(2)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
/* Coached by rainboy */
#include <stdio.h>

#define N 100000

int max(int a, int b) {
	return a > b ? a : b;
}

int main() {
	static char s[N + 1];
	int n, k, i, x;

	scanf("%d%d%s", &n, &k, s);
	x = 1;
	for (i = 1; i < n; i++)
		if (s[i] != s[i - 1])
			x++;
	printf("%d\n", n - max(x - k * 2, 1));
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    ll all = 0;
    rep(i, N) {
        ll tmp;
        cin >> tmp;
        a[i] = tmp;
        all = all ^ tmp;
    }
    rep(i, N) {
        ll tmp = all ^ a[i];
        cout << tmp << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3992
# coding: utf-8

def main():

	# N = 0
	# a = []
	# b = []
	# with open("C:/Users/admin/Downloads/random_05") as f:
	# 	N = int(f.readline())
	# 	a = [int(x) for x in f.readline().split()]
	# 	b = [int(x) for x in f.readline().split()]

	N = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]

	xor_a = [a[i] ^ a[(i+1) % N] for i in range(len(a))]
	xor_b = [b[i] ^ b[(i+1) % N] for i in range(len(b))]

	kmp = KmpSearch(xor_a + xor_a, xor_b)

	ans = kmp.full_search()
	for k in ans:
		if k == len(a):
			break
		print(str(k) + " " + str(a[0 + k] ^ b[0]))

class KmpSearch:
	def __init__(self, target, pattern):
		self.target = target
		self.pattern = pattern
		self.__table = self.__create_kmp_table()

	def full_search(self):
		if len(self.pattern) > len(self.target):
			return -1

		res = []
		i = 0
		p = 0
		while i < len(self.target):
			if self.pattern[p] == self.target[i]:
				i += 1
				p += 1

				if p == len(self.pattern):
					res.append(i-p)
					i -= 1
					p = self.__table[p-1]
			elif p == 0:
				i += 1
			else:
				p = self.__table[p]

		return res

	def __create_kmp_table(self):
		table = [0 for x in range(len(self.pattern))]

		j = 0
		for i in range(1, len(self.pattern)):
			table[i] = j
			if self.pattern[j] == self.pattern[i]:
				j += 1
			else:
				j = 0

		return table

if __name__ == "__main__":
	main()

Measured memory_bytes: 44752
#include <iostream>

using namespace std;

int main() {


	string tmp;
	const char* kai;

	cin >> tmp;

	kai = tmp.c_str();
	int len, cnt;
	cnt = 0;
	len= tmp.length();

	for (int i = 0;i < len / 2;i++) {

		if (kai[i] != kai[len - i - 1]) {
			cnt++;
		}
	}

	cout << cnt << endl;

	return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define PI 3.141592653589793

int main(){
  double a, b, x; cin >> a >> b >> x;
  if(a*a*b /2 <= x){
  	double theta_rad = atan( (2*(a*a*b - x)) / (a*a*a) );
  	double theta = theta_rad * 180.0 / M_PI;
  	cout << setprecision(10) << theta;
  }
  else{
    double theta_rad = atan( 2*(x / (a*b*b) ));
  	double theta = theta_rad * 180.0 / M_PI;
  	cout << setprecision(10) << 90.0 - theta;
  } 
}

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

#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define li long long
#define ld long double
#define x first
#define y second
#define pt pair<int, int>
#define pll pair<li, li>
#define forn(i, t) for(int i = 0; i < (t); i++)
#define fore(i, f, t) for(int i = (f); i < (t); i++)
#define forr(i, f, t) for(int i = (f) - 1; i >= (t); i--)
#define all(x) (x).begin(), (x).end()
#define ins insert

using namespace std;


const int INF = 1e9;
const int MOD = 1e9 + 7;
const li INF64 = 1e18;
const ld EPS = 1e-7;

mt19937 myrand(time(NULL));

const int N = 200 * 1000 + 13;

int n;
int a[N];


bool read(){
	if(scanf("%d", &n) != 1)
		return 0;
	forn(i, n)
		scanf("%d", &a[i]);
	return 1;
}


deque<int> b;


void solve(){
	b = deque<int>();
	forn(i, n)
		if (i % 2 == 0)
			b.pb(a[i]);
		else
			b.push_front(a[i]);
	
	if (n % 2 == 0){
		for (auto it = b.begin(); it != b.end(); ++it)
			printf("%d ", *it);
	}
	else{
		for (auto it = b.rbegin(); it != b.rend(); ++it)
			printf("%d ", *it);
	}
	printf("\n");
}


int main(){
	#ifdef _DEBUG
		freopen("input.txt", "r", stdin);
	#endif
	while(read())
		solve();
	return 0;
}

Measured memory_bytes: 3840
// Problem : A - Calc
// Contest : AtCoder - AtCoder Beginner Contest 172
// URL : https://atcoder.jp/contests/abc172/tasks/abc172_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) begin(x),end(x)

int mod = 1e9+7;
int inf = 4e18;
const int N = 5e5+5;
		
signed main()
{
    io
    int tt = 1;
    //cin>>tt;
    while(tt--)
    {
		int a;
		cin>>a;
		cout<<(a+a*a+a*a*a);		
    }
    return 0;
}


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

int gcd(int a,int b){
  if(b == 0){
    return 0;
  }
 else if(a%b == 0){
    return b;
  }
else{
  return gcd(b, a%b);
}
}


int main(){
	int K;
    cin >> K;
  int sum = 0;
    for(int i=1;i<K+1;++i){
     for(int j=1;j<K+1;++j){
       for(int l=1;l<K+1;++l){
         sum += gcd(gcd(i,j),l);
       }
     }
    }
  cout << sum << endl;
 
}


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

int main() {
  int r, g, b, n, ans = 0;
  cin >> r >> g >> b >> n;
  for(int i = 0; i <= n / r; i++) {
   for(int j = 0; j <= (n - i * r) / g; j++){
      if((n - (i * r) - (j * g)) % b == 0) ans++;
    }
  }
  cout << ans;
}

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

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll x, y; cin >> x >> y;
  auto solve = [&]() -> ll {
    if (x == y) return 0;
    if (x == -y) return 1;
    if (x == 0 && 0 < y) return y;
    if (y == 0 && 0 < x) return 1 + x;
    if (x == 0 && y < 0) return -y + 1;
    if (y == 0 && x < 0) return -x;
    if (0 <= x && x < y) return y - x;
    if (0 <= y && y < x) return 1 + (x - y) + 1;
    if (x < y && y <= 0) return y - x;
    if (y < x && x <= 0) return 1 + (x - y) + 1;
    if (x <= 0 && 0 <= y && -x > y) return (-x - y) + 1;
    if (y <= 0 && 0 <= x && -y > x) return (-y - x) + 1;
    if (x <= 0 && 0 <= y && -x < y) return 1 + y - (-x);
    if (y <= 0 && 0 <= x && -y < x) return 1 + y - (-x);
    assert(0);
  };
  cout << solve() << endl;

  return 0;
}



Measured memory_bytes: 3636