akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

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

long long lcm(long long a,long long b){
	return a*b/gcd(a,b); 
}

/*
int main (){
	long long a,b;cin>>a>>b;
	int c,d;cin>>c>>d;
	int r1=(c-a%c)%c,r2=b%c;
	long long a1=a+r1,b1=b-r2;
    long long ans1=b-a+1-((b1-a1)/c+1);
	r1=(d-a%d)%d;r2=b%d;
	a1=a+r1;b1=b-r2;
	long long ans2=b-a+1-((b1-a1)/d+1);
	long long x=lcm(c,d);
	r1=(x-a%x)%x;r2=b%x;
	a1=a+r1;b1=b-r2;
	long long ans3=b-a+1-((b1-a1)/x+1);
	long long ans=ans1+ans2-ans3;
	cout<<ans<<endl;
	return 0;
}*/

int main (){
	long long a,b;cin>>a>>b;
	int c,d;cin>>c>>d;
	cout<<(b-a+1-(((b-b%c)-(a+(c-a%c)%c))/c+1))+(b-a+1-(((b-b%d)-(a+(d-a%d)%d))/d+1))-(b-a+1-(((b-(b%(lcm(c,d))))-(a+((lcm(c,d))-a%(lcm(c,d)))%(lcm(c,d))))/(lcm(c,d))+1))<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int N;
int A[300005];
int B, W;
int Partial[300005];
void Read()
{
    cin >> N;
    for(int i = 1; i <= N; i++)
    {
        cin >> A[i];
        Partial[i] = Partial[i - 1];
        if(i % 2 == 1)
        {
            B += A[i];
            Partial[i] += A[i];
        }

        else
        {
            W += A[i];
            Partial[i] -= A[i];
        }
    }

}
bool check(int X)
{
    int Min = 0, PMin = 0;
    Partial[N + 1] = Partial[N];
    for(int i = 2; i <= N + 1; i += 2)
    {
        if(Partial[i - 1] - Partial[PMin] >= X)
        {
            if(Min > Partial[i])
            {
                Min = Partial[i];
                PMin = i;
            }
            if(i == N + 1)
                return 1;
        }
    }
    return 0;
}
int binS()
{
    int left = 0, right = B, sol = 0, mid;
    while(left <= right)
    {
        mid = (left + right) / 2;
        if(check(mid) == 1)
        {
            sol = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    int X = max(B, W + sol);
    return X;
}

void Solve()
{
    if(N % 2 == 0)
    {
        cout << max(W, B) << " " << min(W, B) << "\n";
        return;
    }
    int X = binS();
    cout << X << " " << W + B - X << "\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int X;
    cin>>X;
    if(X>=400&&X<=599) cout<<"8";
    else if(X>=600&&X<=799) cout<<"7";
    else if(X>=800&&X<=999) cout<<"6";
    else if(X>=1000&&X<=1199) cout<<"5";
    else if(X>=1200&&X<=1399) cout<<"4";
    else if(X>=1400&&X<=1599) cout<<"3";
    else if(X>=1600&&X<=1799) cout<<"2";
    else if(X>=1800&&X<=1999) cout<<"1";
}


Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <string>
#include <limits.h>
#include <vector>

using namespace std;

int main()
{
    
	long long int a, b;
	cin >> a >> b;

	if (a * b <= 0) {
		cout << "Zero" << endl;
		return 0;
	}

	if (a > 0) {
		cout << "Positive" << endl;
		return 0;
	}

	b -= a;

	if (b % 2 == 1) {
		cout << "Positive" << endl;
	}
	else {
		cout << "Negative" << endl;
	}



	return 0;

}




Measured memory_bytes: 256
n=int(input())
l=[]
d=1
def judge(p):
  for i in range(2,int(p**0.5+1)):
    if p%i==0:
      return False
  return True
cnt=0
while cnt<n:
  if judge(d*10+1):
    l.append(d*10+1)
    cnt+=1
  d+=1
print(*l)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5; 
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}

ll raise(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}


ll n, a[N], b[N], c[N], dp[N][3];

void solve()
{
    cin >> n;
    for (int i=1; i<=n; ++i) cin >> a[i] >> b[i] >> c[i];
    dp[0][1] = 0; dp[0][2] = 0; dp[0][3] = 0;
    for (int i=1; i<=n; ++i) {
        dp[i][1] = max(dp[i-1][2],dp[i-1][3]) + a[i];
        dp[i][2] = max(dp[i-1][1],dp[i-1][3]) + b[i];
        dp[i][3] = max(dp[i-1][2],dp[i-1][1]) + c[i];
    }
    nout(max_3(dp[n][1],dp[n][2],dp[n][3]));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}                       

Measured memory_bytes: 8276
#include <string>
#include <iostream>
#include <stack>
#include <queue> // priority_queue も入ってる
#include <set>   // 要素数は size() で取得 multisetもある
#include <map>
#include <array> // sizeはコンパイル時定数で固定
#include <vector>
#include <numeric>   // accumulate, gcd
#include <algorithm> // count_ifに必要
#include <iomanip>   // cout << setprecision(15) << x で小数の出力精度を指定
#include <tuple>
#include <utility> //pair

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

template <class InputIterator, class T>
bool contains(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

template <class InputIterator>
auto sum(InputIterator iterator)
{
    return accumulate(iterator.begin(), iterator.end(), 0);
}

// endは排他的(exclusive)なので注意
vector<ll> range(ll begin, ll end)
{
    vector<ll> result;
    for (ll i = begin; i < end; ++i)
    {
        result.push_back(i);
    }
    return result;
}

// =========ここまでテンプレ============

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<bool> sunukes(n, false);
    for (ll i = 0; i < k; ++i)
    {
        ll d;
        cin >> d;
        for (ll j = 0; j < d; ++j)
        {
            ll aij;
            cin >> aij;
            --aij;
            sunukes[aij] = true;
        }
    }
    ll count = 0;
    for (bool sunuke : sunukes)
    {
        if (sunuke == false)
        {
            ++count;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define ll long long

int main() {

	int n;
	scanf("%d", &n);
	list<int> li;
	int in;
	if (n & 1) {
		for (int i = 0; i < n; i++) {
			cin >> in;
			i & 1 ? li.push_back(in) : li.push_front(in);
		}
	} else {
		for (int i = 0; i < n; i++) {
			cin >> in;
			i & 1 ? li.push_front(in) : li.push_back(in);
		}
	}
	for (auto it = li.begin(); it != li.end(); ++it)
		cout << *it << ' ';
}


Measured memory_bytes: 9904
from heapq import heapify, heapreplace
N,M=[int(a) for a in input().split()]
A=sorted([int(a) for a in input().split()])
BC=[[int(a) for a in input().split()] for _ in range(M)]
B,C=zip(*sorted(BC, key=lambda row: row[1], reverse=True))
i,j=0,0
for k in range(N):
    if j>=B[i]:
        i+=1
        j=0
    if i>=M or A[k]>= C[i]:
        break
    A[k] = C[i];
    j+=1
print(sum(A))


Measured memory_bytes: 92340
N = int(input())


# ある自然数未満までのエラトステネスの篩をつくる
def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False


def eratosthenes(n):
    s = [True] * n
    for x in range(2, int(n ** 0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0, n) if s[i] and i > 1]


Primes = eratosthenes(55555)
Primes = [p for p in Primes if p % 5 == 1]

print(' '.join(map(str, Primes[:N])))


Measured memory_bytes: 3572
//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
	string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += to_string(x);
	}
	res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
	return "("+to_string(p.f)+", "+to_string(p.s)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
const int INF = 1e9 + 5;
ll MOD;
inline ll powmod(ll a, ll b){ll res=1;for(;b;b>>=1,a=a*a%MOD)if(b&1)res=res*a%MOD;return res;}
inline ll power(ll a, ll b){ll res=1;for(;b;b>>=1,a=a*a)if(b&1)res=res*a;return res;}

const int MAXN = 1e7 + 10;

inline int count(string& x){
	int ans = 0;
	for(char i : x)
		ans += i == '1';
	return ans;
}

inline int rem(string& n, int div){
	if(div == 0)
		return 0;
	MOD = div;
	ll ans = 0;
	for(int i = 0; i < (int)n.size(); i++){
		if(n[i] == '1')
			ans = (ans + powmod(2, i)) % MOD;
	}
	return ans;
}

int dp[MAXN];


int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	for(int i = 1; i < MAXN; i++){
		dp[i] = 1 + dp[i % __builtin_popcount(i)];
	}
	int n;
	string x;
	cin >> n;
	cin >> x;
	reverse(x.begin(), x.end());
	int cnt = count(x);
	ll zero = rem(x, cnt + 1);
	ll one = rem(x, cnt - 1);
	for(int i = n-1; i > -1; i--){
		if(x[i] == '0'){
			MOD = cnt + 1;
			zero += powmod(2, i);
			zero %= MOD;
			cout << 1 + dp[zero] << '\n';
			zero -= powmod(2, i);
			zero += MOD;
			zero %= MOD;
		}
		else{
			MOD = cnt - 1;
			if(MOD == 0){
				cout << 0 << '\n';
				continue;
			}
			one -= powmod(2, i);
			one += MOD;
			one %= MOD;
			cout << 1 + dp[one] << '\n';
			one += powmod(2, i);
			one %= MOD;
		}
	}
}


Measured memory_bytes: 42796
// May this submission get accepted!

#pragma GCC optimize ("O3")
#pragma GCC target ("tune=native")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define STEP(i, is, ie, step) for (long long i=(is), i##_end=(ie), i##_step = (step); i<=i##_end; i+=i##_step)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
template<class T> bool chmax(T &a, const T &b) {if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) {if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) do { cerr << "[DEBUG] " #q ": ["; REP(i, (q).size()) { cerr << (q)[i] << (i == i_len-1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; } while (false)
template<class T> T gcd(T a, T b) { if (a < b) std::swap(a, b); while (b) std::swap(a %= b, b); return a; }
template<class T> T lcm(const T a, const T b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
#define DANCE_ long
#define ROBOT_ unsigned
#define HUMAN_ signed
#define CHOKUDAI_ const
using  ll = DANCE_ HUMAN_ DANCE_;
using ull = DANCE_ ROBOT_ DANCE_;
using cll = DANCE_ DANCE_ CHOKUDAI_;
using  ld = long double;
using namespace std;

// モジュール


// 処理内容
int main() {
    
    // インタラクティブ問題では除去した方がいいかも
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n, a, b; cin >> n >> a >> b;

    if (a == 1 && b == 2) {
        cout << "Borys" << endl;
        return 0;
    }
    
    cout << "Alice\0Borys" + ((b - a) % 2) * 6 << endl;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 998244353;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    
    ll c = a + b;

    ll ans = a*(n/c) + min(a, n%c);

    out(ans);
    re0;
}

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

using namespace std;

const int maxn = 30009;

int data[maxn];

int main()
{
	int n, tmp;
	memset(data, 0, sizeof(data));
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d", &tmp);
		data[tmp] ++;
	}
	bool iss = false;
	for(int i = 0; i <= 10000; i ++)
	{
		while(data[i])
		{
			if(iss)printf(" ");
			else iss = true;
			printf("%d", i);
			data[i] --;
		}
	}
	printf("\n");
	return 0;
}


Measured memory_bytes: 3340
#include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(i=0;i<N;i++)
#define INF 1e9
typedef long long ll;
typedef pair<ll,ll> P;

//素因数分解(O(rootn))
vector<P> prime_factor(ll n){
  vector<P> v;
  for(int i = 2; i<=sqrt(n);i++){
    ll num=0;
    while(n%i==0){ ++num; n/=i; }
    if(num!=0)v.push_back(P(i,num));

  }
  if(n!=1) v.push_back(P(n,1));
  return v;
}

ll gcd(ll a,ll b){
  if(a<0)a=-a;
  if(b<0)b=-b;
  if(b==0)return a;
  else return gcd(b,a%b);
}

//nまでの素数
vector<ll> eratosthenes(ll n){
  int i;
  vector<bool> isprime(n,true);
  vector<ll> res;
  isprime[0]=false;isprime[1]=false;
  REP(i,n){
    if(isprime[i]){
      res.push_back(i);
      for(int j = i*2;j<n;j+=i) isprime[j] = false;
    }
  }
  return res;
}

int main(void){
  int i,N;
  cin >> N;
  N++;
  vector<ll> a(N);
  REP(i,N) cin >> a[i];
  reverse(a.begin(),a.end());

  set<ll> res;

  //f(x) = 0の場合
  ll g = 0;
  //最大公約数
  REP(i,N) g = gcd(g,a[i]);
  //素因数分解して，resに入れていく
  vector<P> m = prime_factor(g);
  REP(i,m.size()) res.insert(m[i].first);

  //N以下の素数pをすべて試す
  vector<ll> era = eratosthenes(N);
  REP(i,era.size()){
    ll p = era[i];
    vector<ll> b(p,0);
    int d;REP(d,p) b[d] = a[d]%p;
    for(d=p;d<N;d++){
      int r = d%(p-1);
      if(r==0)r=p-1;
      b[r] = (b[r] + a[d]%p)%p;
    }

    bool check = true;
    REP(d,p)if(b[d]!=0){check=false;break;}
    if(check)res.insert(p);
  }
  for(auto p : res) cout << p << endl;
  return 0;
}


Measured memory_bytes: 512
function Main(input){
  var N = parseInt(input.split('\n')[0]); // count: A + B
  var K = parseInt(input.split('\n')[1]); // screen + K

  var S = 1; //screen

  for(var i = 0; i < N; i++){
    var A = 2 * S;
    var B = S + K;
    (A < B) ? S = A : S = B;
  }
  console.log(S);
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

ll dp[100005][4];
int main(){

ll n ; 
cin >> n;
ll a[n+1] , b[n+1] , c[n+1]; 
for(ll i=1 ; i<=n ;i++){
     cin >> a[i] >> b[i] >> c[i];
}
dp[0][0]=0;dp[0][1]=0;dp[0][2]=0;dp[0][3]=0;
for(ll i= 1; i <=n ;i++){
 dp[i][1] = max( dp[i-1][2] + a[i], dp[i-1][3] + a[i]);
 dp[i][2] = max( dp[i- 1][1] + b[i], dp[i-1][3] + b[i]);
  dp[i][3] = max( dp[i- 1][1] + c[i], dp[i-1][2] + c[i]);
}

 if(dp[n][1] >= dp[n][2]){cout << max(dp[n][1], dp[n][3]); }
 else {
  cout << max(dp[n][2], dp[n][3]);
 }
}

Measured memory_bytes: 9032
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
#define INF 1e18
typedef long long ll;
typedef pair<int, int> P;

const ll MX =1e18;

int main(){
  ll a;
  double b;
  cin>>a>>b;
  ll ib=b*100+0.5;
  a *=ib;
  a/=100;
  printf("%lld\n",a);
  return 0;

}
    
      
    
  
  
  
  



Measured memory_bytes: 3776
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

int main()
{
  int N, M;
  while(cin >> N >> M, N || M) {
    int now = 1;
    int sizi[N+1]; FOR(i,0,N) cin >> sizi[i+1];
    int me[M]; FOR(i,0,M) cin >> me[i];
    FOR(i,0,M) {
      now += me[i];
      now += sizi[now];
      if(now >= N) {
        cout << i + 1 << endl;
        break;
      }
    }
  }
  return 0;
}

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

int main(void){
  int a,b,c;
  cin>>a>>b>>c;
  if ( b - a >= 2 *c){
    for(int i = a ; i < a + c ; i ++)cout<<i<<endl;
    for(int i = b - c + 1; i < b +1 ; i ++)cout<<i<<endl;
  } else {
    for(int i = a ; i < b + 1 ; i ++)cout<<i<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }

int main(){
    int N;
    cin >> N;
    int ans = 1e9, sum = 0;
    int a[N];
    cins(a, a + N);
    int all = accumulate(a, a + N, 0);
    for(int i = 0; i < N - 1; i++){
        sum += a[i];
        ans = min(ans, abs(all - sum * 2));
    }
    cout << ans << endl;
}


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

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String W = in.readLine();
		int N = Integer.parseInt(W);

		int[] A = new int[N+1];
		int[] B = new int[N+1];
		Arrays.fill(B,0);

		A[0]=0;
		W = in.readLine();
		String[] Ws = W.split(" ");
		for(int i=1;i<N+1;i++){
			A[i]=Integer.parseInt(Ws[i-1]);
		}

		long num = 0;
		int tmp=0;
		for(int i=A.length-1;i>0;i--){
			tmp=0;
			for(int k = 2*i;k<B.length;k=k+i){
				tmp += B[k];
			}
			if(tmp%2 == A[i]){
				B[i]=0;
			}else{
				B[i]=1;
				num++;
			}
		}

		System.out.println(num);
		for(int i=1;i<N+1;i++){
			if(B[i]==1){
				System.out.println(i);
			}
		}
	}

}


Measured memory_bytes: 56064
#include <bits/stdc++.h>
//#include <tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define big bignum
#define lowbit(x) (x & -x)
#define debug(x) (cout << "#x = " << (x) << endl)
#define Set(x, i) memset (x, i, sizeof(x))
#define R register
#define For(i, j, k) for(R int i = (j); i <= (int) (k); ++i)
#define Rep(i, j, k) for(R int i = (j); i >= (int) (k); --i)
#define Cross(i, j, k) for(R int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
const ll N = 100011;
const ll INF = 5e16;

namespace IO {

	inline char gc() {
		static char buf[100000], *p1 = buf, *p2 = buf;
		return (p1 == p2) && (p2 = (p1 = buf) +
			fread(buf, 1, 100000, stdin), p1 == p2)? EOF: *p1++;
	}

	#define dd ch = getchar()
	inline ll read() {
		R ll x = 0; R int f = 0; R char dd;
		for (; !isdigit(ch); dd) f ^= (ch == '-');
		for (; isdigit(ch); dd)  x = x * 10 + (ch ^ 48);
		return f? -x: x;
	}
	#undef dd

	inline void write ( ll x ) {
		if (x < 0) x = -x, putchar('-');
		if (x > 9) write(x / 10); putchar(x % 10 | 48);
	}

	inline void wrn ( ll x ) { write(x), putchar(' '); }

	inline void wln ( ll x ) { write(x), putchar('\n'); }

	inline void wlnn ( ll x, ll y ) { wrn(x), wln(y); }

}

using IO::wln;
using IO::read;

namespace Cesare {
	
	int main() {
		ll n = read();
		if (n & 1) printf("%.8lf\n", 1.0 * (n / 2 + 1) / n);
		else printf("%.8lf\n", 0.5000000000000);
		return 0;
	}
	
}

int main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	return Cesare :: main();
}

/*

*/






Measured memory_bytes: 764
#include<stdio.h>
int main(void){
  int i,N,count=0;
  int p[50];
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&p[i]);
    if(p[i]!=i+1){
      count++;
    }
  }
  if(count<=2){
    printf("YES\n");
  }else{
    printf("NO\n");
  }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include<algorithm>
#include<sstream>
#include<iomanip>


using namespace std;



int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, int>>> pref(n);
	vector<string> id_city(m);
	for (int i = 0; i < m; i++) {
		int p, y;
		cin >> p >> y;
		p--;
		pref[p].emplace_back(make_pair(y, i));
	}

	for (int i = 0; i < n; i++) {
		sort(pref[i].begin(), pref[i].end());
		int num = 1;
		for (pair<int, int> p_y : pref[i]) {
			stringstream ss;
			ss << setfill('0') << right << setw(6) << i+1;
			ss << setfill('0') << right << setw(6) << num;
			id_city[p_y.second] = ss.str();
			num++;
		}
	}

	for (int i = 0;i < m; i++) {
		cout << id_city[i] << endl;
	}
	
}

Measured memory_bytes: 12416
#define _USE_MATH_DEFINES
#include<cstdio>
#include<cmath>
using namespace std;

int main(){
    int a, b, x;
    scanf("%d %d %d", &a, &b, &x);
    if(x*2 >= a*a*b){
        printf("%Lf\n", atan((long double)(2*(a*a*b - x))/(long double)(a*a*a))/M_PI*180.0);
    }else{
        printf("%Lf\n", atan((long double)(a*b*b)/(long double)(2*x))/M_PI*180.0);
    }
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <string>
using namespace std;
using ll = long long;

int main() {
  string S;
  string s[2] = {"dream", "erase"};
  cin >> S;
  int n = S.size(), p = -1;
  for (int i=0; i<n; i++) {
    if (S[i] == 'd')
      if (S.compare(i, 5, s[0]) == 0) {
        p = 0;
        i += 4;
      } else {
        cout << "NO" << endl;
        return 0;
      }
    else if (S[i] == 'e') {
      if (S.compare(i, 5, s[1]) == 0) {
        p = 1;
        i += 4;
      } else if (p == 0 && S[i+1] == 'r') {
        p = -1;
        i++;
      }
    } else if (p == 1 && S[i] == 'r')
      p = -1;
    else {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
  return 0;
}

Measured memory_bytes: 512
import java.util.*;import java.io.*;import java.math.*;

public class Main
{

    public static void process()throws IOException
    {
        int k=ni(),n=ni(),arr[]=new int[n+1];
        for(int i=1;i<=n;i++) arr[i]=ni();
        long x=k-arr[n]+arr[1];//the area unexplored

        long pref[]=new long[n+1],suff[]=new long[n+1];

        for(int i=2;i<=n;i++) pref[i]=pref[i-1]+(arr[i]-arr[i-1])*1l;

        long res=pref[n];

        for(int i=n-1;i>=1;i--) suff[i]=suff[i+1]+(arr[i+1]-arr[i])*1l;

        res=Math.min(res, suff[1]);

        for(int i=2;i<=n-1;i++) res=Math.min(res, pref[i]+suff[i+1]+x);
        pn(res);
    }


       static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        out = new PrintWriter(System.out);
        sc=new AnotherReader();
        boolean oj = true;

        //oj = System.getProperty("ONLINE_JUDGE") != null;
        if(!oj) sc=new AnotherReader(100);

        long s = System.currentTimeMillis();
        int t=1;
        while(t-->0)
            process();
        out.flush();
        if(!oj)
            System.out.println(System.currentTimeMillis()-s+"ms");
        System.out.close();  
    }

    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);System.out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
    static boolean multipleTC=false;



/////////////////////////////////////////////////////////////////////////////////////////////////////////

    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
    
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
    
    
    

Measured memory_bytes: 47696
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use std::process::exit;
use std::cmp::*;
use itertools::Itertools;

fn main() {
    let a: i32 = read!();
    let b: i32 = read!();
    let c: i32 = read!();
    let d: u32 = read!();
    let e: i32 = max(a,max(b,c));
    println!("{}",a+b+c-e+e*2_i32.pow(d))
}

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

int main () {
  int N ;
  cin >> N ;
  int line[N] ;
  int pre = 1 ;
  for(int i = 0 ; i < N ; i++ ) cin >> line[i] ;
  for(int i = 0 ; i < N ; i++ ) 
    if(line[i]%2==0)
      pre *= 2 ;
  cout << pow(3,N) - pre << endl ;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>

using namespace std;
#define REP(i, n) for (int i = 0; i < n; i++)

int w, h;
int C[50][50] = {};

void visit(int x, int y) {
  C[x][y] = 0;
  for (int ix = x - 1; ix <= x + 1; ix++) {
    for (int iy = y - 1; iy <= y + 1; iy++) {
      if (ix >= 0 && iy >= 0 && ix < w && iy < h && C[ix][iy] == 1) {
        visit(ix, iy);
      }
    }
  }
}

int main() {
  while (cin >> w >> h, w) {
    int ans = 0;
    C[50][50] = {};
    REP(j, h) {
      REP(i, w) { cin >> C[i][j]; }
    }
    REP(i, w) {
      REP(j, h) {
        if (C[i][j] == 1) {
          ans++;
          visit(i, j);
        }
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 3260
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  priority_queue<int> nega;
  priority_queue<int> posi;
  rep(i, n){
    cin >> a[i];
    if(a[i]>=0){
      posi.push(-a[i]);
    } else {
      nega.push(a[i]);
    }
  }
  int negasz=nega.size();
  ll ans=0;
  int tmp;
  if(negasz%2==1 && !posi.empty()) {
    tmp=nega.top();
    int tmp2=posi.top();
    nega.pop();
    posi.pop();
    if(tmp<tmp2){
      ans-=tmp;
      ans+=tmp2;
    } else {
      ans+=tmp;
      ans-=tmp2;
    }
  } else if(negasz%2==1 && posi.empty()){
    tmp=nega.top();nega.pop();
    ans+=tmp;
  }
  while(!nega.empty()){
    tmp=nega.top();nega.pop();
    ans-=tmp;
  }
  while(!posi.empty()){
    tmp=posi.top();posi.pop();
    ans-=tmp;
  }
  cout << ans << endl;
  return 0;
}


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

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

int sum;
int d;

int main(int argc, char *argv[])
{
  while(cin >> sum, sum){
    rep(i, 9){
      cin >> d;
      sum -= d;
    }
    cout << sum << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
int main() {
	int n, m, p;
	while (cin >> n >> m >> p&&n + m + p != 0) {
		int sum = 0;
		int t = 0, x;
		for (int i = 0; i < n; i++) {
			cin >> x;
			sum += x;
			if (i == m - 1) t = x;
		}
		if (t != 0) {
			cout << floor(sum*(100 - p) / t) << endl;
		}
		else cout << 0 << endl;
	}
} 

Measured memory_bytes: 3192
w,h,*L=map(int,open(0).read().split())
P=L[:w];Q=[-qj for qj in L[w:]]
x,y,ans=w,h,0
for c in sorted(P+Q,key=abs):
	if c>0:
		if x:ans+=c*(y+1);x-=1
	else:
		if y:ans-=c*(x+1);y-=1
print(ans)

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

string s;int x,h;
int main(){
	ios::sync_with_stdio(0);
	cin>>s;
	for(int i=0;i<s.size();++i){
		x=x*10+s[i]-48;
		h+=s[i]-48;
	}
	if(x%h==0)puts("Yes");else puts("No");
}

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

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
using lll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
  lll ii,jj,kk;
  vector<int> ret;
  lll n;
  vector<lll> l;
  cin >> n;
  l.resize(n);

  for(ii=0;ii<n;ii++){
    cin >> l[ii];
  }
  lll sum = 0;
  sort(l.begin(),l.end());//,std::greater<lll>());
  //cout << "end sort" << endl;
  vector<lll> tmp;

  for(ii=n-1;ii>=2;ii--){
    for(jj=ii-1;jj>=1;jj--){
      for(kk=jj-1;kk>=0;kk--){
        if(l[jj]+l[kk]>l[ii]){
          sum++;
        }
      }
    }
  }
//      tmp.resize(n-(jj));
//
//      for(kk=0;kk<tmp.size()-1;kk++){
//        tmp[kk] = l[jj+1+kk];
//      }
//      auto up1 = upper_bound(l.begin()+jj+1,l.end(),l[ii]-l[jj]);
//      lll num = up1-l.begin();
//      //cout << num << endl;
//      sum += n - num;
////      for(kk=0;kk<tmp.size()-1;kk++){
////        if(l[jj]+tmp[kk]>l[ii]){
////          sum++;
////        }
////      }
//      
//    }
//  }
  
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(_i,_a,_n) for(int _i=_a;_i<=_n;++_i)
#define PER(_i,_a,_n) for(int _i=_n;_i>=_a;--_i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(_a) ({REP(_i,1,n) cout<<_a[_i]<<',';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



#ifdef __APPLE__
const int N = 1e2+50;
#else
const int N = 1e6+50;
#endif




int main() {
	char s[222];
	cin>>s;
	s[3]=0;
	cout<<s<<endl;
}









Measured memory_bytes: 3636
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60

typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-9, pi = acos(-1.0);
namespace std {
    bool operator<(const Point &lhs, const Point &rhs) {
        if (lhs.real() < rhs.real() - eps) return true;
        if (lhs.real() > rhs.real() + eps) return false;
        return lhs.imag() < rhs.imag();
    }
}
Point input_point() {ld x, y; cin >> x >> y; return Point(x, y);} // ????????\???
bool eq(ld a, ld b) {return (abs(a - b) < eps);} // ????????????????????????
ld dot(Point a, Point b) {return real(conj(a) * b);} // ??????
ld cross(Point a, Point b) {return imag(conj(a) * b);} // ??????

// ??´????????????
class Line {
public:
    Point a, b;
    Line() : a(Point(0, 0)), b(Point(0, 0)) {}
    Line(Point a, Point b) : a(a), b(b) {}
    Point operator[](const int _num) {
        if (_num == 0)return a;
        else if (_num == 1)return b;
        else assert(false);
    }
};

// ????????????
class Circle {
public:
    Point p;
    ld r;
    Circle() : p(Point(0, 0)), r(0) {}
    Circle(Point p, ld r) : p(p), r(r) {}
};

// CCW
int ccw(Point a, Point b, Point c) {
    b -= a; c -= a;
    if (cross(b, c) > eps) return 1;   // a,b,c??????????¨???¨?????????????????¶
    if (cross(b, c) < -eps) return -1; // a,b,c???????¨???¨?????????????????¶
    if (dot(b, c) < 0) return 2;       // c,a,b???????????´???????????¶
    if (norm(b) < norm(c)) return -2;  // a,b,c???????????´???????????¶
    return 0;                          // a,c,b???????????´???????????¶
}

/* ????§???¢ */
typedef vector<Point> Polygon;
// ??????
Polygon convex_hull(vector<Point> ps) {
    int n = (int)ps.size();
    if(n < 3) return ps;
    sort(ps.begin(), ps.end());
    Polygon u = {ps[0], ps[1]},l = {ps[n-1],ps[n-2]};
    for(int i = 2; i < n; i++){
        for(int j = (int)u.size(); j>=2 && ccw(u[j-2],u[j-1],ps[i])>=0;j--)u.pop_back();
        u.push_back(ps[i]);
    }
    for(int i = n-3;i>=0;i--){
        for(int j = (int)l.size(); j>=2 && ccw(l[j-2],l[j-1],ps[i])>=0;j--)l.pop_back();
        l.push_back(ps[i]);
    }
    reverse(l.begin(),l.end());
    for(int i=(int)u.size()-2; i>= 1; i--)l.push_back(u[i]);
    return l;
}

int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    int n; cin >> n;
    Polygon ps;
    for(int i = 0; i < n;i++) ps.emplace_back(input_point());
    Polygon ret = convex_hull(ps);
    
    /* ???????§???¢???????????§????????????????????????????????§??????????????????????????????????????????????¨?????????§????????§?¨??????????*/
    cout << ret.size() << endl;
    int idx = 0;
    for(int i = 1; i < (int)ret.size();i++){
        if( ret[idx].imag() > ret[i].imag() || (ret[idx].imag() == ret[i].imag() && ret[idx].real() > ret[i].real())){
            idx = i;
        }
    }
    for(int i = idx; i < idx + (int)ret.size();i++){
        cout << ret[i%(int)ret.size()].real() << " " << ret[i%(int)ret.size()].imag() << endl;
    }
    return 0;
}

Measured memory_bytes: 15752
#include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        long  x , y;
        cin >> x >> y;
        long ans;
        ans = 0;
        if(x == y){
            
        }else if((x < 0 && y > 0) || (x >= 0 && y <= 0)){
            ans = abs(x + y) + 1;
        }else{
            ans = abs(x - y);
            if(x > y){
                ans += 2;
            }
        }
        cout << ans << endl;
        
        return 0;
    }

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
	mod            = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n := nextInt()
	a := nextInts(n)

	s := make([]int, n)
	for i := 0; i < n; i++ {
		s[i] = a[i]
		if i > 0 {
			s[i] += s[i-1]
		}
	}

	ans := 0
	for i := 0; i < n; i++ {
		pow := (s[n-1] - s[i]) % mod
		ans += (a[i] * pow) % mod
		ans %= mod
	}

	puts(ans)
}


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

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

using namespace std;

const int MAX_N = 101;
const int IINF = INT_MAX;

int N,T;
string s[MAX_N];
int score[MAX_N],cnt[MAX_N];
char a[6][6];
bool used[6][6];
int dp[10010];

void dfs(int x,int y,int depth,int limit,int index){
  if( depth >= limit ) {
    ++cnt[index];
    return;
  }
  REP(dx,-1,2){
    REP(dy,-1,2){
      if( dx == 0 && dy == 0 ) continue;
      int nx = x + dx, ny = y + dy;
      if( !( 0 <= nx && nx < 4 && 0 <= ny && ny < 4 ) ) continue;
      if( used[ny][nx] || a[ny][nx] != s[index][depth] ) continue;
      used[ny][nx] = true;
      dfs(nx,ny,depth+1,limit,index);
      used[ny][nx] = false;
    }
  }
}

void compute(){
  rep(i,N) rep(y,4) rep(x,4) if( a[y][x] == s[i][0] ) {
    used[y][x] = true;
    dfs(x,y,1,(int)s[i].size(),i);
    used[y][x] = false;
  }

  rep(i,T+1) dp[i] = -IINF;
  dp[0] = 0;
  int maxi = 0;
  rep(i,N){
    int len = (int)s[i].size();
    for(int t=T;t>=0;t--) if( dp[t] != -IINF ) {
      for(int use=0;t+use*len<=T&&use<=cnt[i];use++){
        dp[t+use*len] = max(dp[t+use*len],dp[t]+use*score[i]);
        maxi = max(maxi,dp[t+use*len]);
      }
    }
  }
  cout << maxi << endl;
}

int main(){
  cin >> N;
  rep(i,N) cin >> s[i] >> score[i];
  rep(i,4) {
    string line;
    cin >> line;
    rep(j,4) a[i][j] = line[j];
  }
  cin >> T;
  compute();
  return 0;
}

Measured memory_bytes: 1252
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

string s,t;
int f[3030][3030];
pii from[3030][3030];
int lens,lent;

void dfs(int x,int y){
    if(x<= 0 || y<=0) return ;
    dfs(from[x][y].fs,from[x][y].sc);
    cout<<s[x];
}
int main(){
    // debug;
    ios;
    cin>>s>>t;
    lens = s.length(),lent = t.length();
    s = "#" + s; t = "^"+t;
    for(int i = 1;i<=lens;i++){
        for(int j = 1;j<=lent;j++){
            if(s[i] == t[j]) {
                f[i][j] = f[i-1][j-1] + 1;
                if(s[i-1] == t[j-1]) from[i][j] = {i-1,j-1};
                else from[i][j] = from[i-1][j-1];
            }else{
                f[i][j] = max(f[i-1][j],f[i][j-1]);
                if(f[i-1][j] > f[i][j-1]){
                    if(s[i-1] == t[j]) from[i][j] = {i-1,j};
                    else from[i][j] = from[i-1][j];
                }else{
                    if(s[i] == t[j-1]) from[i][j] = {i,j-1};
                    else from[i][j] = from[i][j-1];
                }
            } 
        }
    }
    int x = from[lens][lent].fs,y = from[lens][lent].sc;
    dfs(x,y);
    if(s[lens] == t[lent]) cout<<s[lens];

    
    return 0;
}


Measured memory_bytes: 107648
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<math.h>
#include<set>

#define REPS(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)

using namespace std;

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

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

signed main() {
	string str;
	int K;
	cin >> str >> K;

	set<char> alphabet_set;
	set<string> ans_set;

	// 文字列に使われているアルファベットを列挙
	REP(i, str.size()) {
		alphabet_set.insert(str[i]);
	}

	// 1文字目がi番目のアルファベットの部分文字列をsetに追加
	for(char alphabet : alphabet_set) {

		// strのj文字目を探索
		REP(j, str.size()) {
			if (str[j] == alphabet) {
				
				// 部分列をsetに追加
				int length = min((int)str.size() - j + 1, 50);
				REPS(k, 1, length) {
					ans_set.insert(str.substr(j, k));
				}
			}
		}
		if (ans_set.size() >= K) break;
	}

	int count = 0;
	for (string st : ans_set) {
		count++;
		if (count == K) {
			cout << st;
			break;		}
	}
	system("pause");
	return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reps(i,a,b) for(int i= a; i < b; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
  int h, w;
  cin >> h >> w;
  vector<string> vec(h, "");
  rep(i, h) cin >> vec.at(i);
  vector<vector<pair<int, int>>> mp(h, vector<pair<int, int>>(w, make_pair(0, 0)));
  rep(i, h) {
    int j = 0;
    while(j < w) {
      if (vec.at(i).at(j) == '#') {
        j++;
        continue;
      }

      int k = j;
      int cnt = 0;
      while(k < w && vec.at(i).at(k) == '.') {
        cnt++;
        k++;
      }
      int tmp = k;
      k--;
      while(k >= j) {
        mp.at(i).at(k).first = cnt;
        k--;
      }
      j = tmp;
    }
  }
  rep(i, w) {
    int j = 0;
    while(j < h) {
      if (vec.at(j).at(i) == '#') {
        j++;
        continue;
      }
      int k = j;
      int cnt = 0;
      while(k < h && vec.at(k).at(i) == '.') {
        cnt++;
        k++;
      }
      int tmp = k;
      k--;
      while(k >= j) {
        mp.at(k).at(i).second = cnt;
        k--;
      }
      j = tmp;
    }
  }
  int ans = 0;
  rep(i, h) {
    rep(j, w) {
      ans = max(ans, mp.at(i).at(j).first + mp.at(i).at(j).second - 1);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 42232
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cctype>
using namespace std;

int main(void){
    int a, b;
    cin >> a >> b;
    int l[a];
    for(int i = 0; i < a; i++)
        cin >> l[i];
    int sum = 0;
    int ans = 1;
    for(int i = 0; i < a; i++){
        sum += l[i];
        if(sum <= b)
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 300001
using namespace std;
int n,mxx,mxy,sx[N],sy[N];
vector<int>gx,gy;
map<pair<int,int>,char>mp;
int main(void){
	int i,x,y;scanf("%d%d%d",&x,&y,&n);
	while(n--)scanf("%d%d",&x,&y),mxx=max(mxx,++sx[x]),mxy=max(mxy,++sy[y]),mp[make_pair(x,y)]=1;
	for(i=1;i<=300000;++i)if(sx[i]==mxx)gx.push_back(i);
	for(i=1;i<=300000;++i)if(sy[i]==mxy)gy.push_back(i);
	for(int x:gx)for(int y:gy)if(!mp.count(make_pair(x,y)))return printf("%d\n",mxx+mxy),0;//至少一对不重合 
	printf("%d\n",mxx+mxy-1);//都必定重叠 
	return 0;
}


Measured memory_bytes: 28596
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
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; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;


int main(){

ll k,x;
cin >> k >> x;
if(500*k>=x)cout << "Yes" << endl;
else cout << "No" << endl;

return 0;
}


Measured memory_bytes: 256
S = input()
result = "Yes"
for i in range(len(S)):
    if i % 2 == 0:
        if S[i] == "L":
            result = "No"
            break
    elif i % 2 != 0:
        if S[i] == "R":
            result = "No"
            break
print(result)

Measured memory_bytes: 3064
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;



int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    if(a == b){
        cout << c << "\n";
    }else{
        if(a == c) cout << b << "\n";
        else cout << a << "\n";
    }

    return 0;
}


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

int main(){
    int H, W, M;
    cin >> H >> W >> M;
    vector<int> hcnt(H), wcnt(W);
    vector<pair<int, int>> bomb;
    for(int i = 0; i < M; i++){
        int h, w;
        cin >> h >> w;
        h--, w--;
        bomb.emplace_back(h, w);
        hcnt[h]++, wcnt[w]++;
    }
    ll hmx = 0, hnum = 0;
    for(int i = 0; i < H; i++){
        if(hmx < hcnt[i]) hmx = hcnt[i];
    }
    for(int i = 0; i < H; i++){
        if(hcnt[i] == hmx) hnum++;
    }
    ll wmx = 0, wnum = 0;
    for(int i = 0; i < W; i++){
        if(wmx < wcnt[i]) wmx = wcnt[i];
    }
    for(int i = 0; i < W; i++){
        if(wcnt[i] == wmx) wnum++;
    }
    int cnt = 0;
    for(auto b : bomb){
        int h = b.first;
        int w = b.second;
        if(hcnt[h] == hmx && wcnt[w] == wmx){
            cnt++;
        }
    }
    if(cnt < hnum * wnum){
        cout << hmx + wmx << endl;
    } else {
        cout << hmx + wmx - 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 9788