akhauriyash/Code-Regression huggingface dataset:
// abc170_f
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF (ll)(1e9)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int dx[8]={ 1, 0, -1, 0, -1, 1, -1, 1};
int dy[8]={ 0, 1, 0, -1, -1, -1, 1, 1};

bool bound_check(int i, int j, int N, int M) {return (0 <= i) && (i < N) && (0 <= j) && (j < M);}

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int H, W, K;
    cin >> H >> W >> K;
    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    sx--; sy--; gx--; gy--;
//    vector<vector<bool>> S(H, vector<bool>(W, true));
    vector<string> S(H);
    REP(i, H) cin >> S[i];


    vector<int> dist(H*W, INF);
    dist[sx*W+sy] = 0;

    priority_queue<P, vector<P>, greater<P>> pq;
    pq.push(P(0, sx*W+sy));

    vector<vector<vector<bool>>> search_num(H, vector<vector<bool>>(W, vector<bool>(4, true)));

    while (!pq.empty()){

        P p = pq.top(); pq.pop();

        int cost = p.first;
        int k = p.second;
        int i = k / W;
        int j = k % W;
//        print(i+1, j+1, cost);

        if (i == gx && j == gy){
//            REP(u, 3) {
//                REP(v, 5){
//                    cout << dist[u*W+v] << " ";
//                }
//                cout << endl;
//            }
            print(cost);
            return 0;
        }

        REP(d, 4){
            if (not search_num[i][j][d]) continue;

            int n = 1;
            while (true) {
                int ni = i + dx[d] * n;
                int nj = j + dy[d] * n;

                if (not bound_check(ni, nj, H, W)) break;
                if (S[ni][nj] == '@') break;

                int ncost = cost + (n + K - 1) / K;
                int v = ni * W + nj;
                if (ncost < dist[v]){
                    dist[v] = ncost;
                    pq.push(P(ncost, v));
                    // 今進んできた方向は探す必要ない。
                    search_num[ni][nj][d] = false;
                    search_num[ni][nj][(d+2)%4] = false;
                } else if (ncost == dist[v]) {
                    ;
                } else {
                    break;
                }
                n++;
            }
        }
    }

    print(-1);


    return 0;
}


Measured memory_bytes: 148672
n = int(input())
a = list(map(int,input().split()))

even = [[i,0] for i in range(10**5+1)]
odd = [[i,0] for i in range(10**5+1)]
for e,o in zip(a[::2],a[1::2]):
    even[e][1] += 1
    odd[o][1] += 1

even.sort(key=lambda x: -x[1])
odd.sort(key=lambda x: -x[1])

if even[0][0] != odd[0][0]:
    print(n-even[0][1]-odd[0][1])
else:
    print(n-max(even[0][1]+odd[1][1],even[1][1]+odd[0][1]))

Measured memory_bytes: 34972
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
#S = str(input())
r, D, x2000 = map(int, input().split())

def f(x) :
  global r
  global D
  return (r*x - D)

x = f(x2000)
for i in range(10):
  print (x)
  x = f(x)



Measured memory_bytes: 3572
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int cnt = 0;
        int curMax = 0;
        for(int i = 0; i < n; i++) {
        	if(i == 0) {
        		cnt++;
        		curMax = sc.nextInt();
        		continue;
        	}
        	int num = sc.nextInt();
        	if(curMax >= num) {
        		cnt++;
        		curMax = num;
        	}
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 62844
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	int a,b;
	cin >> a >> b;
	if((a&1)^(b&1)){
		cout << "IMPOSSIBLE" << endl;
	}else{
		cout << ((a+b)>>1) << endl;
	}
	return 0;
}


Measured memory_bytes: 256
//2006
#include<iostream>
using namespace std;
int main(void){
	int i,s[31]={0},a=0;
	for(i=1;i<29;i++){
		cin>>a;
		s[a]=1;
	}
	for(i=1;i<31;i++){
		if(s[i]!=1)
		{
			cout<<i<<endl;
		}
	}
	return 0;
}//vuin @icloud.com,@gmail.com


Measured memory_bytes: 3096
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

int main(){
  int N, Q; cin >> N >> Q;
  string S; cin >> S;

  vector <int> cnt(N);
  for (int i = 1; i < N; i++){
    cnt[i] = cnt[i - 1];
    if (S[i - 1] == 'A' && S[i] == 'C'){
      cnt[i]++;
    }
  }

  vector <int> ans(Q);
  for (int i = 0; i < Q; i++){
    int A, B; cin >> A >> B;
    A--; B--;
    ans[i] = cnt[B] - cnt[A];
  }
  
  for (int i = 0; i < Q; i++){
    cout << ans[i] << endl;
  }
  
  
  return 0;
}


Measured memory_bytes: 1792
def root(x):
  while par[x]>=0:x=par[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x!=y:
    if x>y:x,y=y,x
    par[x]+=par[y]
    par[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return-par[root(x)]
n,m,k,*t=map(int,open(0).read().split())
par=[-1]*n
f=[set()for _ in range(n)]
for a,b in zip(*[iter(t[:m*2])]*2):
  a-=1
  b-=1
  unite(a,b)
  f[a].add(b)
  f[b].add(a)
a=[size(i)-len(f[i])-1for i in range(n)]
for c,d in zip(*[iter(t[m*2:])]*2):
  c-=1
  d-=1
  if same(c,d):
    a[c]-=1
    a[d]-=1
print(*a)

Measured memory_bytes: 62996
import * as fs from 'fs';

const input: string = fs.readFileSync('/dev/stdin', 'utf8');
const args: string[][] = input.split('\n').map(l => l.split(' '));

const k = parseInt(args[0][0]);
console.log(getLunlun(k));

function getLunlun(n: number): number {
  function getNum(ns: number[]): number {
    return ns.reduce((x, y) => 10 * x + y)
  }

  let tmp = n - 1;
  let a: number[][] = [];
  for (let i = 1; i <= 9; i++) a.push([i]);
  if (tmp < a.length) return getNum(a[tmp])

  const nextNumbers: number[][] = [];
  for (let i = 0; i < 10; i++) {
    const tmp: number[] =
      [i + 9, i, i + 1]
        .map(x => x % 10)
        .filter(x => Math.abs(i - x) <= 1)
        .sort((x, y) => x - y);
    nextNumbers.push(tmp);
  }

  while (tmp >= a.length) {
    tmp -= a.length;
    let tmpArray: number[][] = [];
    a.forEach(array => {
      const nexts: number[] = nextNumbers[array[array.length - 1]];
      nexts.forEach(x => {
        tmpArray.push([...array, x]);
      })
    });
    a = tmpArray;
  }
  return getNum(a[tmp])
}

Measured memory_bytes: 56652
def main():
    N, P = map(int, input().split())
    if N == 1:
        print(P)
        return
    if N >= 40:
        print(1)
        return

    i = 2
    retval = 1
    while P > 1 and i**N <= P:
        cnt = 0
        while P % i == 0:
            cnt += 1
            P //= i
        retval *= i ** (cnt // N)
        i += 1
    print(retval)


if __name__ == "__main__":
    main()


Measured memory_bytes: 39408
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void solve() {
  int n;
  cin >> n;
  vector<string> s(n);
  rep(i,n) cin >> s[i];
  int m;
  cin >> m;
  vector<string> t(m);
  rep(i,m) cin >> t[i];
  map<string, int> count;
  rep(i,n) count[s[i]]++;
  rep(i,m) count[t[i]]--;
  int ans = 0;
  for (auto u: count) {
    ans = max(ans, u.second);
  }
  cout << ans << endl;
}

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

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

int main(){
  int n,q,i;
  string s;
  cin >> n >> q >> s;
  vector<int> a(n+1,0);
  a.at(0)=0;
  a.at(1)=0;
  for(i=2;i<=n;i++){
    if(s.at(i-2)=='A'&&s.at(i-1)=='C'){
      a.at(i)=a.at(i-1)+1;
    }else{
      a.at(i)=a.at(i-1);
    }
  }
  
  int l,r,m;
  for(i=0;i<q;i++){
    cin >> l >> r;
    if(l>1&&s.at(l-2)=='A'&&s.at(l-1)=='C'){
      m=1;
    }else{
      m=0;
    }
    cout << a.at(r)-a.at(l-1)-m << endl;
  }
}
    

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

typedef long long ll;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
bool ISINT(double x){return fabs(x-(int)round(x))<EPS;}
bool ISEQ(double x,double y){return fabs(x-y)<EPS;}
string itos(ll x){stringstream ss;ss<<x;return ss.str();}
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

typedef pair<int,int> P;

int n;
int x[200002];
int y[200002];
P s[200002];

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

  while (cin >> n) {
    for (int i = 0; i < n; i++) {
      cin >> x[i];
      s[i] = P(x[i], i);
    }

    sort(s, s + n);

    for (int i = 0; i < n; i++) {
      y[s[i].second] = i;
    }

    int med = n / 2;
    
    for (int i = 0; i < n; i++) {
      if (y[i] < med) {
        cout << s[med].first << endl;
      } else {
        cout << s[med - 1].first << endl;
      }
    }
  }
}


Measured memory_bytes: 5376
#include<stdio.h>

int main(){

	int a[11],b,i,j,k,l;
	

	for(i=1;i<=10;i++){
		scanf("%d",&a[i]);
	}
	for(j=10;j>1;j--){
		for(k=1;k<j;k++){
			if(a[k+1]<a[k])b=a[k],a[k]=a[k+1],a[k+1]=b;
		}
	}
	for(l=10;l>7;l--){
		printf("%d\n",a[l]);
	}
        return 0;

} 

Measured memory_bytes: 0
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
typedef vector<ll> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//do {
//    print(v);
//  } while (std::next_permutation(v.begin(), v.end()));


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

	int N;
	cin >> N;
	int ans = INF;
	eFOR(i, 1, N - 1) {
		int cnt = 0;
		int a = N - i;
		int b = i;
		while (true) {
			cnt += a % 10;
			a /= 10;
			if (a < 10) {
				cnt += a;
				break;
			}
		}
		while (true) {
			cnt += b % 10;
			b /= 10;
			if (b < 10) {
				cnt += b;
				break;
			}
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}




















Measured memory_bytes: 256
#include <cstdio>
#include <utility>
#include <cctype>
#include <vector>
#include <string>
using namespace std;

#ifdef __linux
#define _U(s) s##_unlocked
#else
#define _U(s) _##s##_nolock
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#define gcu _U(getchar)
#define pcu _U(putchar)
#define _DEF(r, n, ...) inline r n(__VA_ARGS__) noexcept
#define _T template <typename T>
#define _HT template <typename H,typename... T>
#define _OP(t) inline operator t()
struct _in {
#ifdef _GLIBCXX_STRING
	_OP(string){string s;char c;while(isspace(c = gcu()));do{s+=c;}while(c=gcu(),c!=' '&&c!='\n'&&c!=EOF);return s;}
#define _S
#endif
	_OP(char){char c=gcu();gcu();return c;}
	_OP(double){double d; scanf("%lf",&d); gcu();return d;}
	_T _OP(T){T n{},m{1},c;while(isspace(c = gcu()));if(c=='-')m=-1,c=gcu();do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
} in;
#define _SCAN(...) _DEF(bool,scan,__VA_ARGS__)
#ifdef _S
_SCAN(string &o) {int c{gcu()};if(c==EOF)return false;else{ungetc(c,stdin);string t=move(in);o=t;return true;}}
#endif
_T _SCAN(T &o) {int c{gcu()};return c==EOF?false:(ungetc(c,stdin),o=in,true);}
_HT _SCAN(H &h,T&&... t){return scan(h)&&scan(t...);}
#define _OUT(...) _DEF(void,out,__VA_ARGS__)
#define _OUTL(...) _DEF(void,outl,__VA_ARGS__)
_OUT(bool b){pcu('0'+b);}
_OUT(const char *s){while(*s)pcu(*s++);}
_OUT(char c){pcu(c);}
#ifdef _S
_OUT(string &s){for(char c:s)pcu(c);}
#endif
_T _OUT(T n){static char b[20];char *p=b;T m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=(char)(n%10*m+'0'),n/=10;while(p!=b)pcu(*--p);}
_OUTL(){out('\n');}
#ifdef _GLIBCXX_VECTOR
	_T _OUT(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);}
#endif
_HT _OUT(H &&h, T... t){out(h);out(t...);}
template <typename... T> _OUTL(T... t){out(t...);outl();}
struct range{
	int e,b=0,s=1;range(int _b,int _e,int _s):e(_e),b(_b),s(_s){} range(int _b,int _e): e(_e), b(_b){} range(int _e):e(_e){}
	struct it{int v,s; it(int _v,int _s):v(_v),s(_s){} operator int()const{return v;} operator int&(){return v;}int operator*()const{return v;}
		it& operator++(){v+=s;return *this;} }; it begin(){return {b,s};} it end(){return {e,s};}};
#define times(i,n) for(int i=n;i;i--)

template <typename T>
using V = vector<T>;

string cmp(string &a, string &b) {
	return a.size() == b.size() ? max(a, b) : a.size() > b.size() ? a : b;
}

int main() {
	for (int W, H; W = in, H = in;) {
		V<V<char>> C(H + 1, V<char>(W + 1));
		for (int i: range(H)) {
			for (int j: range(W))
				C[i][j] = gcu();
			gcu();
		}
		V<V<string>> d(H + 1, V<string>(W + 1));
		string r;
		for (int i: range(H - 1, -1, -1))
			for (int j: range(W - 1, -1, -1))
				if (isdigit(C[i][j])) {
					string &t {d[i][j]};
					t = C[i][j] + cmp(d[i + 1][j], d[i][j + 1]);
					if (t.size() && t[0] != '0')
						r = cmp(r, t);
				}
		outl(r);
	}
}


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

int main(int argc, const char * argv[]) {
    int N, L;
    int eat;
    int i;
    int ans = 0;
    
    cin >> N >> L;
    
    if(L >= 0){
        eat = L;
    } else if(N + L > 0){
        eat = 0;
    } else {
        eat = N + L - 1;
    }
    
    for(i=0; i<N; i++){
        ans += (L + i);
    }
    
    cout << ans - eat;
    
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

int main(){
    fast;
    ll a, b, n, x;
    cin >> a >> b >> n;
    if(n >= b)
        x = b-1;
    else
        x = n; 
    ll ans = (a*x)/b;
    cout << ans;
    return 0;
}


Measured memory_bytes: 3640
#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define setpre(a) cout.precision(a),cout<<fixed;
#define ALL(a) a.begin(),a.end()
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

int n, m, k, ans;
string s[100];

int main() {Tie
    cin >> n >> m >> k;
    for(int i = 0; i < n ; i++)
        cin >> s[i];
    int sn = 1 << n, sm = 1 << m;
    for(int i = 0; i < sn; i++) {
        for(int j = 0; j < sm; j++) {
            bitset<7> x = i, y = j;
            // cout << x << ' ' << y << '\n';
            int cnt = 0;
            for(int k = 0; k < n; k++) {
                for(int l = 0; l < m; l++) {
                    if(s[k][l] == '#' && !x[k] && !y[l]) {
                        cnt++;
                    }
                }
            }
            if(cnt == k)
                ans++;
        }
    }
    cout << ans << '\n';
}


Measured memory_bytes: 3652
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> P;

int main(){
  int n,m,mat[1000][100];

  while(true){
    vector<P> v;
    int array[1000] = {0};
    cin >> n >> m;
    if(!n&&!m) break;

    for(int i = 0 ; i < n ; i++)
      for(int j = 0 ; j < m ; j++)
	mat[i][j] = 0;

    for(int i = 0 ; i < n ; i++)
      for(int j = 0 ; j < m ; j++)
	cin >> mat[i][j];

    for(int i = 0 ; i < n ; i++){
      for(int j = 0 ; j < m ; j++){
	if(mat[i][j]) ++array[j];
      }
    }

    for(int i = 0 ; i < m ; i++){
      v.push_back(P(-array[i],i+1));
    }
    sort(v.begin(),v.end());

    for(int i = 0 ; i < v.size() ; i++){
      if(!i) cout << v[i].second;
      else cout << " " << v[i].second;
    }
    cout << endl;
  }

  return 0;
}

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

int main(){
    int n; cin >> n;
    int count2 = 0, count4 = 0, count0 = 0;
    for(int i = 0; i < n; i++){
        ll a; cin >> a;
        if(a % 4 == 0){
            count4++;
        }else if(a % 2 == 0){
            count2++;
        }else{
            count0++;
        }
    }
    if(n % 2 == 1 && (count4 == count0-1) && count2 == 0){
        cout << "Yes" << endl;
        return 0;
    }
    if(n % 2 == 1 && (count4 == count0-1) && count2 != 0){
        cout << "No" << endl;
        return 0;
    }
    if(count4 >= count0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

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

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;

const int N = 112345;
const int MOD = 1e9 + 7;

inline int getInt() {
  int x;
  scanf("%d", &x);
  return x;
}

int main() {
  int h = getInt();
  int w = getInt();
  vector<string> a(h);
  for (string &s : a) {
    cin >> s;
  }
  vector<vector<int>> b(h, vector<int>(w, 0));
  vector<vector<int>> c(h, vector<int>(w, 0));
  vector<vector<int>> d(h, vector<int>(w, 0));
  vector<vector<int>> ans(h, vector<int>(w, 0));
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (i == 0 && j == 0) {
        b[i][j] = a[i][j] == '#';
        c[i][j] = a[i][j] == '.';
        d[i][j] = min(b[i][j], c[i][j]);
      } else if (i == 0) {
        b[i][j] = b[i][j - 1] + (a[i][j] == '#' && a[i][j - 1] != '#');
        c[i][j] = c[i][j - 1] + (a[i][j] == '.' && a[i][j - 1] != '.');
        d[i][j] = min(b[i][j], c[i][j]);
      } else if (j == 0) {
        b[i][j] = b[i - 1][j] + (a[i][j] == '#' && a[i - 1][j] != '#');
        c[i][j] = c[i - 1][j] + (a[i][j] == '.' && a[i - 1][j] != '.');
        d[i][j] = min(b[i][j], c[i][j]);
      } else {
        b[i][j] = min(b[i - 1][j] + (a[i][j] == '#' && a[i - 1][j] != '#'), b[i][j - 1] + (a[i][j] == '#' && a[i][j - 1] != '#'));
        c[i][j] = min(c[i - 1][j] + (a[i][j] == '.' && a[i - 1][j] != '.'), c[i][j - 1] + (a[i][j] == '.' && a[i][j - 1] != '.'));
        d[i][j] = min(b[i][j], c[i][j]);
      }
      //cout << "(" << b[i][j] << ", " << c[i][j] << "), ";
    }
    //cout << "\n";
  }
  printf("%d\n", min(b[h - 1][w - 1], 1000+c[h - 1][w- 1]));
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ull unsigned long long int
#define ll long long
#define int long long
#define ld long double
#define endl '\n'
const int mod= 1e9+7;
#define F first
#define S second
//#define x first
//#define y second
#define pb push_back
#define mp make_pair
#define trace(x) cerr << #x << " is " << x << endl;
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<"\n";
#define all(x) x.begin(),x.end()
#define reset(x,val) memset(x,val,sizeof(x))
#define flush fflush(stdout)
#define sz(a) a.size()
#define pii pair<int,int>
void fail(){std::cout<<"NO\n";exit(0);}
using namespace std;
int n,k;
const int N=1e5+5;
int dp[105][N],pre[N];
int a[105];
int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL); 
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
  
    for(int j=0;j<=k;j++)
    {
     if(j<=a[1])
     dp[1][j]=1;
     pre[j]=pre[j-1]+dp[1][j];
     pre[j]%=mod;
    }
    //for(int i)
    pre[-1]=0;
    for(int i=2;i<=n;i++)
    {
     for(int j=0;j<=k;j++)
     {
      int l=max(0LL,j-a[i]),r=j;
//      if(j==5)
//      {
//       trace3(l,r,pre[r]);
//      }
      dp[i][j]+=pre[r]-pre[l-1]+mod;
      dp[i][j]%=mod;
      //trace3(i,j,dp[i][j]);
     }
     reset(pre,0);
     //pre[0]=dp[i][0];
     for(int j=0;j<=k;j++)
     {
      pre[j]=pre[j-1]+dp[i][j];
      pre[j]%=mod;
     } 
    }
    cout<<dp[n][k]<<endl;
    return 0; 
}


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

using namespace std;
typedef long long ll;

#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++)


int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    const int inf = 1e9;
    const int hmax = 20002;
    int h, n;
    cin >> h >> n;
    int a[n], b[n];

    rep(i, n)
    {
        cin >> a[i] >> b[i];
    }

    vector<vector<int>> dp_list;
    vector<int> v;

    rep(i, hmax + 1)
        v.push_back(inf);
    rep(i, n + 1)
        dp_list.push_back(v);
    rep(i, n + 1)
        dp_list[i][0] = 0;

    rep(i, n)
        rep(j, hmax + 1)
        {
            if (j - a[i] >= 0)
                dp_list[i + 1][j] = min(dp_list[i][j], dp_list[i + 1][j - a[i]] + b[i]);
            else
                dp_list[i + 1][j] = dp_list[i][j];
            
        }

    // rep(i, n + 1)
    // {
    //     rep(j, hmax + 1)
    //             cout
    //         << dp_list[i][j] << " ";
    //     cout << endl;
    // }
    int ans = inf;
    rep2(j, h, hmax+1)
        ans = min(ans, dp_list[n][j]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 78592
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int n,m;
  cin>>n>>m;
  priority_queue<long long int> a;
  for(long long int i=0; i<n; i++){
    long long int x;
    cin>>x;
    a.push(x);
  }

  for(int i=0; i<m; i++){
    long long int x=a.top();
    a.pop();
    x/=2;
    a.push(x);
  }

  long long int ans=0;
  for(int i=0; i<n; i++){
    ans+=a.top();
    a.pop();
  }

  cout<<ans<<endl;
}

Measured memory_bytes: 1400
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>
#include <queue>
#include <list>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define crep(i) for(char i='a';i<='z';i++)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define psortfirst(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.first<b.first;});
#define ALL(x) (x).begin(),(x).end()
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
using namespace std;
using pii  = pair<int,int>;
long long gcd(long long a, long long b){return (b == 0 ? a : gcd(b, a%b));}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
typedef long long ll;
#define MOD 1000000007
#define EPS 10e-8

map<ll,ll> M;

int main(){
  ll N,A[107],B[107],sum=0,ans=0;
  cin >> N;
  rep(i,N){
    cin >> A[i];
  }
  rep(i,N){
    cin >> B[i];
  }
  rep(i,N){
    sum=0;
    for(int j=0;j<=i;j++){
      sum+=A[j];
    }
    for(int j=i;j<N;j++){
      sum+=B[j];
    }
    ans=max(sum,ans);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int H = scan.nextInt();
        int W = scan.nextInt();
        char[][] map = new char[H][W];
        for (int i = 0; i < H; i++) {
            String s = scan.next();
            char[] d = s.toCharArray();
            for (int j = 0; j < W; j++) {
                map[i][j] = d[j];
            }
        }
        for (int i = 0; i < H - 1; i++) {
            for (int j = 0; j < W - 1; j++) {
                if (map[i][j] == '#' && map[i][j+1] == '#' && map[i+1][j] == '#' && map[i+1][j+1] == '#') {
                    System.out.println("Impossible");
                    return;
                }
                if (map[i][j] == '#' && map[i][j+1] == '#' && map[i+1][j] == '#' && map[i+1][j+1] == '.') {
                    System.out.println("Impossible");
                    return;
                }
                if (map[i][j] == '.' && map[i][j+1] == '#' && map[i+1][j] == '#' && map[i+1][j+1] == '#') {
                    System.out.println("Impossible");
                    return;
                }
            }
        }
        System.out.println("Possible");
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n-1); i >= 0; i--)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;

const int D = 60;

int main(){
    ll N, K; cin >> N >> K;
    vector<vector<int>> to(60, vector<int>(N,0));
    rep(i,N) cin >> to[0][i];
    rep(i,N) to[0][i]--;

    rep(i,59){
        rep(j,N){
            to[i+1][j] = to[i][to[i][j]];
        }
    }

    int current = 0;
    for(int i = D-1; i>=0; i--){
        ll l = 1LL << i;
        if (l <= K){
            current = to[i][current];
            K -= l;
        }
    }

    cout << current + 1 << endl;
}

    

Measured memory_bytes: 51048
n = int(input())
a = list(map(int,input().split()))
a = a + [0]

a.sort(reverse = True)

b = 1
ichi = 0
r = []
for i in range(n):
    if a[i] != a[i+1]:
        if b != 1:
            r.append(b)
        else:
            ichi += 1
        b = 1
    else:
        b += 1

for i in range(len(r)-1):
    if r[i] % 2 == 0:
        r[i] = 1
        r[i+1] -= 1
    else:
        r[i] = 1
        
if r != []:
    if r[-1] % 2 == 0:
        print(ichi + len(r) - 1)
    else:
        print(ichi + len(r))
        
else:
    print(ichi)

Measured memory_bytes: 53572
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N,M; cin>>N>>M;
    if(N>M) swap(N,M);

    int ans;
    if(N==1){
        if(M==1) ans=1;
        else ans=M-2;
    }
    else{
        ans=(N-2)*(M-2);
    }
    cout<<ans<<endl;

}


Measured memory_bytes: 256
#include<stdio.h>
 
#define MAX 101
#define WHITE -1
#define GRAY 0
#define BLACK 1
 
int n,t;
int color[MAX],d[MAX],f[MAX],Adj[MAX][MAX];
 
dfs(){
  int i;
 
  for(i=0;i<n;i++) color[i]=WHITE;
  t=0;
  for(i=0;i<n;i++){
    if(color[i]==WHITE) visit(i);
  }
}
 
visit(int r){
  int i;
 
  color[r]=GRAY;
  d[r]=++t;
 
  for(i=0;i<n;i++){
    if(Adj[r][i]==1 && color[i]==WHITE) visit(i);
  }
 
  color[r]=BLACK;
  f[r]=++t;
}
 
int main(){
  int i,u,k,j,v;
 
  for(i=0;i<MAX;i++){
    for(j=0;j<MAX;j++){ 
      Adj[i][j]=0;
    }
  }
 
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      Adj[u-1][v-1]=1;
    }
  }
 
  dfs();
 
  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,d[i],f[i]);
  }
 
  return 0;
}

Measured memory_bytes: 640
/*
 *
 *   Author     : Amit Kumar
 *   Date    	: June 4 2019
 * 
 */

#include <bits/stdc++.h>

//#define FAST_INPUT_OUTPUT
//#define MORE_THAN_ONE_TESTCASE // COMMENT IT

#define vi vector<int>
#define vl vector<long long>
#define mii map<int , int>
#define mll map<long long , long long>
#define msi map<string , i>
#define msl map<string , long long>
#define umii unordered_map<int,int>
#define umll unordered_map<long long ,long long>
#define umsi unordered_map<string , int>
#define umsl map<string , long long> 
#define si set<int>
#define sl set<long long>
#define pii pair<int , int >
#define psi pair<string,int>
#define psl pair<string , long > 
#define pll pair<long long , long long>
#define vpii vector<pii>
#define vpll vector<pll>
#define vpsi vector<psi>
#define vpsl vector<psl>
#define pqi priority_queue<int>
#define pql priority_queue<long long>
#define ub upper_bound
#define lb lower_bound
#define bint long long int
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define iv(v) for(auto &i:v){cin>>i;}
#define ov(v) for(auto i:v){cout<<i<<" ";}cout<<endl;
#define ovn(v) for(auto i:v){cout<<i<<endl;}
#define euv(v) for(auto i:v){cerr<<i<<" ";}cerr<<endl;
#define eovn(v) for(auto i:v){cerr<<i<<endl;}
#define os(s) for(auto itr:s){cout<<itr<<" ";}cout<<endl;
#define osn(s) for(auto itr:s){cout<<itr<<endl;}
#define eos(s) for(auto itr:s){cerr<<itr<<" ";}cerr<<endl;
#define eosn(s) for(auto itr:s){cerr<<itr<<endl;}
#define rep(x) for(auto i=0 ; i<(x); ++i)
#define _rep(a,b) for(auto i=(a); i<(b); ++i)
#define endl '\n'
using namespace std;




auto SOLUTION_FUNCTION( void ) ->void {

    // your solution goes here 

    bint n;
    cin>>n;

    vl v(5);

    iv(v);

    bint counter=0 ;
    --n;
    rep(5){
        counter = max(counter , n/v[i]);
    }
    cout<<counter+5<<endl;

    return ;
}




int main(void){
#ifdef FAST_INPUT_OUTPUT
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout<<setprecision(10);
    cout<<fixed;
    cout<<boolalpha;
#endif
#ifdef MY_LOCAL_PROJECT
    freopen("cin","r",stdin);
    freopen("cout","w",stdout);
#endif
    int testcase = 1;


#ifdef MORE_THAN_ONE_TESTCASE
    cin>>testcase;
#endif
    
    while(testcase--){
        SOLUTION_FUNCTION();
    }

#ifdef MY_LOCAL_PROJECT
    cout<<"Time : "<<1.0*(double)clock()/CLOCKS_PER_SEC<<endl;
#endif
    return 0;
}


Measured memory_bytes: 256
n = int(input())
s = input()

count = 0
for i in s:
    if i == ")":
        count += 1
    else:
        s = "(" * count + s
        if count > 0:
            count = -1
        else:
            count -= 1

if count > 0:
    s = "(" * count + s
elif count < 0:
    s = s + ")" * -count

print(s)

Measured memory_bytes: 2940
import numpy as np
import heapq

# n = int(input())
# V = list(map(int, input().split()))

s = input()
l = len(s)

f1 = '10'*(l//2)
f2 = '01'*(l//2)

if l%2 == 1:
    f1 += '1'
    f2 += '0'

s = int(s, 2)    

print(min(format(s ^ int(f1, 2), 'b').count('1'), format(s ^ int(f2, 2), 'b').count('1')))
      


Measured memory_bytes: 12728
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstring>
#include <cstdio>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map> //pair is also included in this library
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define REP(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define fst first
#define snd second
#define MP make_pair //incase c++11 or later is not available

using namespace std;

typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//prefer define statement
//for reason that const int ver. of INF will raise a silly warning (unused variable)
#define INF (INT_MAX/3)
#define LIM_INF (INT_MAX)
//const int INF = INT_MAX/3;
#define PI = 3.14159265358979323846
/*------------------------------------------------------------------------------*/

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

bool is_special_gcd(int array[], int size, int sum){
  REP(i, 0, size){
    if(gcd(sum-array[i], array[i]) == 1){
      return false;
    }
  }
  return true;
}

int main(){
  int N;

  cin >> N;

  if(N == 3){
    cout << "2 5 63" << endl;
    return 0;
  } else if(N == 4){
    cout << "2 5 20 63" << endl;
    return 0;
  }

  VI vec(0);

  REP(i, 0, 14999){
    vec.push_back(2 * (i+2));
  }

  REP(i, 0, 4999){
    vec.push_back(3 * ((2 * (i + 1)) + 1));
  }

  random_device seed_gen;
  mt19937 engine(seed_gen());
  
  int array[30000] {2, 3};

  while(1){
    shuffle(vec.begin(), vec.end(), engine);

    int sum = 5;
    REP(i, 2, N){
      array[i] = vec[i-2];
      sum += array[i];
    }

    if(is_special_gcd(array, N, sum)){
      sort(array, array+N);
      REP(i, 0, N){
        cout << array[i] << " ";
      }
      cout << endl;
      return 0;
    }
  }
  
  return 0;
}


Measured memory_bytes: 640
//1.read question_2.read I/O_3.read test cases_4.read constraints(to decide TC of solution)_5.decide method_6.dry run_
//7.code_8.test_9.submit
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define mod 1000000007
#define F first
#define S second
#define _READ freopen("input.txt","r", stdin);
#define pb push_back
#define MP make_pair
#define _FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int main()
{
   
    _FAST
    lli n,t,i,j,k,ans=0,flag=0,a,b,m;
    cin>>n;vector<lli> ar(n);
    for(auto &i:ar)
        cin>>i;
    vector<vector<lli>> dp(n,vector<lli>(n,0));
    for(i=n-1;i>=0;i--)
        for(j=i;j<n;j++)
        if(i==j)
            dp[i][j]=ar[i];
        else
        dp[i][j]=max(ar[i]-dp[i+1][j],
                     ar[j]-dp[i][j-1]);
    cout<<dp[0][n-1];
    return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	int n,k; cin>>n>>k;

	if(2*k>n+1){ cout<<-1<<'\n'; return 0; }

	vector<int> a(n),b(n),c(n);
	int num=k+3*n;
	rep(i,n) c[n-i-1]=--num;
	rep(i,n) b[(i+k)%n]=--num;

	vector<pair<int,int>> p(n);
	rep(i,n) p[i]={c[i]-b[i],i};
	sort(p.rbegin(),p.rend());

	rep(i,n) a[p[i].second]=--num;

	rep(i,n) cout<<a[i]<<' '<<b[i]<<' '<<c[i]<<'\n';

	return 0;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++) 
#define all(v) begin(v),end(v)
using ll = long long;

int main() {
  string s;cin>>s;
    if(s=="KIHBR"||s=="AKIHBR"||s=="KIHABR"||s=="KIHBAR"||s=="KIHBRA"||s=="AKIHABR"||s=="AKIHBAR"||s=="AKIHBRA"||s=="KIHABAR"||s=="KIHABRA"||s=="KIHBARA"||s=="AKIHABAR"||s=="AKIHABRA"||s=="AKIHBARA"||s=="KIHABARA"||s=="AKIHABARA")cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
    int r,g;
    cin >> r >> g;
    cout << 2*g-r << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int X, Y;
	cin >> X >> Y;
	int ans = 0;
	for(int i=0;i<=X;i++){
		if(Y == i * 2 + (X - i) * 4)ans++;
	}
	if(ans > 0)cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 3592
import sys
from heapq import heappush, heappushpop

readline = sys.stdin.readline


def solve():
    N = int(readline())

    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        K, L, R = map(int, readline().split())
        if L > R:
            ans += R
            left[K - 1].append(L - R)
        else:
            ans += L
            if 0 <= N - K - 1:
                right[N - K - 1].append(R - L)

    for vec in (left, right):
        hq = []
        n = len(vec)

        for i in range(n):
            for p in vec[i]:
                if len(hq) >= i + 1:
                    heappushpop(hq, p)
                else:
                    heappush(hq, p)

        for i in range(n, N):
            for p in vec[i]:
                if len(hq) >= n:
                    heappushpop(hq, p)
                else:
                    heappush(hq, p)

        ans += sum(hq)

    return ans


def main():
    T = int(readline())

    ans = [0] * T
    for i in range(T):
        ans[i] = solve()

    print('\n'.join(map(str, ans)))
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 107516
n = int(input())
for i in range(1,n+1):
    if i%3 == 0:
        if i == n or i == n-1 or i == n-2:
            print(" "+str(i))
        else:
            print(" "+str(i),end="")
    elif i%10 == 3:
        if i == n or i == n-1 or i == n-2:
            print(" "+str(i))
        else:
            print(" "+str(i),end="")
    elif str(i).find("3") > -1:
        if i == n or i == n-1 or i == n-2:
            print(" "+str(i))
        else:
            print(" "+str(i),end="")

Measured memory_bytes: 7996
class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

N, M, K = map(int, input().split())
if N == M == K == 0:
    exit()
MOD = 998244353
comb = Combination(N + K)

ans = 0
for k in range(K + 1):
    L = N - k
    ans += M * pow(M - 1, L - 1, MOD) * comb.nhr(L, k)
    ans %= MOD
print(ans)

Measured memory_bytes: 59436
/*
 * Contents   : AOJ DPL 1 H
 * Author     : Kitaura Hiromi
 * LastUpdate : 20180625
 * Since      : 20180625
 */
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>
typedef long long ll;
using namespace std;
ll v[40], w[40];
ll INF = (1<<20);
pair<ll, ll> ps[1<<20]; // sw, svを保持
ll N, W;
int main(void){
    cin >> N >> W;
    for(int i=0; i<N; i++) cin >> v[i] >> w[i];
    // 前半分の2^N/2を全探索
    for(int i=0; i<1<<N/2; i++){
        ll sw=0, sv=0;
        for(int j=0; j<N/2; j++){
            if(i>>j & 1){
                sw += w[j];
                sv += v[j];
            }
        }
        ps[i] = make_pair(sw, sv);
    }
    // sw[i] <= sw[j]かつsv[i] >= sv[j]なるjを取り除く
    sort(ps, ps+(1<<N/2));
    int m = 1;
    for(int i=1; i<1<<N/2; i++){
        if(ps[m-1].second < ps[i].second){
            ps[m++] = ps[i];
            // ps[i] = ps[m++];
        }
    }
    // 後ろ半分の2^N/2を全探索
    ll res = 0;
    for(int i=0; i<1<<(N-N/2); i++){
        ll sw=0, sv=0;
        for(int j=0; j<(N-N/2); j++){
            if(i>>j & 1){
                sw += w[N/2+j];
                sv += v[N/2+j];
            }
        }
        if(sw <= W){
            ll tv = (lower_bound(ps, ps+m, make_pair(W-sw, INF)) - 1)->second;
            res = max(res, sv+tv);
        }
    }
    printf("%lld\n", res);
}


Measured memory_bytes: 19612
#include<bits/stdc++.h>
using namespace std;
 typedef pair<long long,int> Pair; 
 const int maxn=2007;

 int N;
const int M=-1000000000000000;
 vector<Pair> A;
 long long f[maxn][maxn];

 long long dp(int x,int y)
 { 
   if(x==0&&y==0) return 0;
   if(f[x][y]!=M) return f[x][y];
   if(y==0) 
     f[x][y]=A[x+y-1].first*(A[x+y-1].second-x)+dp(x-1,y);
   if(x==0)
     f[x][y]=(-1)*A[x+y-1].first*(A[x+y-1].second-N-1+y)+dp(x,y-1);
   if(x>0&&y>0)
   {  f[x][y]=max(A[x+y-1].first*(A[x+y-1].second-x)+dp(x-1,y),(-1)*A[x+y-1].first*(A[x+y-1].second-N-1+y)+dp(x,y-1));
   }
   return f[x][y];
 }
     
   
 
int main()
{
  long long  i,j,k,ma;
  ma=0;
  cin>>N;
  
  for(i=0;i<N;i++)
  {
    cin >> k;
    A.push_back({k,i+1});
  }
  
   sort(A.begin(),A.end());
   reverse(A.begin(),A.end());
  
  for(i=0;i<maxn;i++)
  {
    for(j=0;j<maxn;j++)
    {
       f[i][j]=M;
    }
  }
  
  for(i=0;i<=N;i++)
  {
    ma=max(dp(i,N-i),ma);
  }
    
 /* for(i=0;i<=N;i++)
  {
    for(j=0;j<=N-i;j++)
    {
      cout << f[i][j] <<" "  ;
      if(i+j==N) cout << endl;
    }
  }*/
  cout << ma << endl;
    
  
  
  
  
  
}

Measured memory_bytes: 35252
#include<stdio.h>
int main(){
    long long N,A,B,num;
    scanf("%lld %lld %lld",&N,&A,&B);
    num=N%(A+B);
    if(num<A){
        printf("%lld\n",(N/(A+B))*A+num);
    }else{
        printf("%lld\n",(N/(A+B))*A+A);
    }
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define LiangJiaJun main
using namespace std;
int n,ans=0;
void dfs(int c3,int c5,int c7,int x,int n){
     if(c3==0&&c5==0&&c7==0){
        if(x<=n)++ans;
        return ;
     }
     if(x>n)return ;
     if(c3>0){
        dfs(c3-1,c5,c7,x*10+3,n);
     }
     if(c5>0){
        dfs(c3,c5-1,c7,x*10+5,n);
     }
     if(c7>0){
        dfs(c3,c5,c7-1,x*10+7,n);
     }
}
int LiangJiaJun(){
    scanf("%d",&n);
    int jp=n,len=0;
    while(jp){
        ++len;
        jp/=10;
    }
    for(int i=1;i<=len;i++)
        for(int j=1;i+j<=len;j++)
            for(int k=1;i+j+k<=len;k++)
                dfs(i,j,k,0,n);
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)

ll rec[10005];

int main(){
    ll n, m;
    cin >> n >> m;
    
    map<ll, priority_queue<ll>> que;
    rep(i, n){
        ll a, b;
        cin >> a >> b;
        que[a].push(b);
    }
    
    ll ans = 0;

    priority_queue<pair<ll, ll>> buff;
    for(ll day = 1; day <= m; day++){

        if(que.count(day) > 0){
            buff.push(make_pair(que[day].top(), day));
            que[day].pop();
        }

        if(!buff.empty()){
            auto p = buff.top();
            cerr << p.first << p.second << endl;
            ans += p.first;
            buff.pop();
            if(!que[p.second].empty()){
                auto q = que[p.second].top();
                buff.push(make_pair(q, p.second));
                que[p.second].pop();
            }
        }
    
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 11008
#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; }

string s;
void input(){
    fast_io();
    cin >> s;
}

int solve(){
    char now = 'S';
    vector<int> cal;
    int num = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if(s[i]==now) num++;
        else{
            now = s[i];
            cal.push_back(num);
            num = 1;
        }        
    }
    cal.push_back(num);
    cal.push_back(0);
    DBG(cal)
    for (int i = 0; i < cal.size()-1; i++)
    {
        if(i%2==0){
            int m = 0;
            m = min(cal[i],cal[i+1]);
            cal[i] -= m;
            cal[i+1] -= m;
        }
        else{
            if(cal[i]==0)
            cal[i+1] += cal[i-1];
            cal[i-1] = 0;
        }
    }
    int ans = accumulate(cal.begin(),cal.end(),0);
    cout << ans << endl;
    
    return 0;
}   

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

Measured memory_bytes: 1044
program ABC_088_A_InfiniteCoins
   implicit none
   integer N, A, r
   read(*, *) N, A
   if(mod(N, 500) <= A)then
	  write(*, *) 'Yes'
   else
	  write(*, *) 'No'
   end if
end program ABC_088_A_InfiniteCoins 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r)for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r)for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k)for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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 dy[]={0, 1, 0, -1};                                 // 4方向近傍
int dx[]={1, 0, -1, 0};                                 // 4方向近傍

int main(){
    double n, m, d, ans; cin >> n >> m >> d;
  	if(d == 0) ans = (m-1) / n;
    else if(d >= n) ans = 0;
    else ans = (m-1)*2*max(n-d,0) / (n*n);
  	// m-1 : 計算する隣り合う数の総和
  	// max(n-d,0) : 隣り合う数で組み合わせを動かして、どれだけ美しさを得られるか
    // pow(n,m-2) : 隣り合う数以外で任意で動かせる組み合わせ
    cout << fixed << setprecision(10) << ans << endl;
}


Measured memory_bytes: 256