akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>

#include <algorithm>
#include <numeric>
#include <cmath>

using namespace std;
typedef long long ll;
const long double PI = (acos(-1));
const long long MOD = 1000000007;

static const int  MAX_INT = std::numeric_limits<int>::max();
static const long MAX_LONG = std::numeric_limits<long>::max();
static const ll   MAX_LL = std::numeric_limits<long long>::max();

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

///////////////////////////////////////////////////
// ------------------- utils ------------------- //
///////////////////////////////////////////////////
// change min/max
template<class T> inline bool chMin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chMax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

///////////////////////////////////////////////////
// ------------------- main -------------------- //
///////////////////////////////////////////////////
void Main() {
    ll D, T, S; cin >> D >> T >> S;
    cout << (T * S >= D ? "Yes" : "No")  << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout << std::fixed << std::setprecision(15);
    Main();

    double tmp;
    cin >> tmp;

    return 0;
}


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

#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef long long ll;


int main(){

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

    int n;
    cin >> n;
    vector<double> p;
    p.resize(n);

    for(auto &i:p) cin >> i;

    // dp[i] = probability of having i heads so far
    // can use 1d space using same idea as knapsck 1D
    vector<double> dp(n+1);
    dp[0] = 1;

    for(int coin=0; coin < n; coin++){
        for(int numHeads=coin+1; numHeads >= 0; numHeads--){

            if(numHeads == 0) dp[0] = dp[0] * (1-p[coin]);
            else 
                dp[numHeads] = dp[numHeads-1] * p[coin] + dp[numHeads] * (1-p[coin]);

        }
    }

    double ans=0;

    for(int heads=0; heads <= n; heads++){
        int tails = n-heads;
        if(heads > tails) ans += dp[heads];
    }

    cout.precision(10);
    cout << ans << endl;

    return 0;
}

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

#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<cstring>
#include<climits>
#include<queue>
#include<algorithm>
#include<iomanip>
#define ll long long int
#define endl '\n'

using namespace std;

vector<int> ar[100001];
const int maxN = 17;
int parent[100001],vis[100001]={0};
int cnt=1;

void dfs(int node,int par)
{

	parent[node] = par;
    vis[node]=1;

	for(int i:ar[node]){
        if(vis[i]==0){
            dfs(i,node);
        }
	}



}

void bfs(int node,int par){

    parent[node] = par;
    vis[node]=1;
    queue<int> q;
    q.push(node);
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        //cout<<cur<<" ";
        for(int i=0;i<ar[cur].size();i++){
            if(vis[ar[cur][i]]==0){
                vis[ar[cur][i]]=1;
                q.push(ar[cur][i]);
                parent[ar[cur][i]]=cur;
                cnt++;

            }
        }
    }

}


int main()
{
	int n,a,b,q,x,y;

	cin>>n>>q;




	for(int i=0;i<=n;i++){
		vis[i]=0;
		ar[i].clear();
	}
	for(int i=1;i<=q;i++){
		cin>>x>>y;
		ar[x].push_back(y);
		ar[y].push_back(x);
	}
    bfs(1,-1);
   //cout<<"cnt "<<cnt<<endl;

    if(cnt!=n){
        cout<<"No"<<endl;
    }
    else{
            cout<<"Yes"<<endl;
        for(int i=2;i<=n;i++){
            cout<<parent[i]<<endl;
        }
    }

}


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

int main() {
  int n;
  int ans;
  
  //ページ数の入力
  cin >> n;
  if(n%2==0) {
    ans=n/2;
  }
  else {
    ans=(n/2)+1;
  }
  
  //答えを出力
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
### constant

MAX_P = 10 ** 6

### subroutines

def gen_primes(max_p)
  primes = Array.new(max_p + 1){true}
  primes[0] = primes[1] = false

  s_max_p = Math.sqrt(max_p + 0.5).to_i

  for p in (2..s_max_p)
    if primes[p]
      for q in (p * p).step(max_p, p)
        primes[q] = false
      end
    end
  end

  primes
end

### main

primes = gen_primes(MAX_P)
pnums = (2..MAX_P).select{|p| primes[p]}
#p pnums.length; exit

loop do
  l = gets.to_i
  break if l == 0

  count = 1

  for pn in pnums
    break if l == 1

    f = 0
    while l % pn == 0
      l /= pn
      f += 1
    end

    if f > 0
      count *= ((f + 1) * 2 - 1)
    end
  end

  if l > 1
    count *= 3
  end

  puts (count + 1) / 2
end

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

string convert(string s) {
	s += "#";
	string res = "";
	
	int size = s.size(), cur = -1, len = 0;
	
	for_(i,0,size) {
		if (s[i] - '0' != cur) {
			if (cur != -1) {
				stringstream ss;
				ss << len << cur;
				res += ss.str();
			}
			
			cur = s[i] - '0';
			len = 1;
		} else {
			++len;
		}
	}
	
	return res;
}

int main() {
	int n;
	string s;
	
	while (cin >> n, n) {
		cin >> s;
		
		for_(i,0,n) s = convert(s);
		
		cout << s << endl;
	}
}

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

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;

const int CASES = 4;

bool check(const string& S, int p){
    for(int i = p+1;i < S.size(); ++i) {
        int tmp = (int)(S[i]-'0');
        if(tmp != 9){
            return true;
        }
    }
    return false;
}

void solve(){
    string N; cin >> N;
    int n = N.size();
    if(n == 1){
        cout << N << endl;
        return;
    }

    bool flag = false;
    int ans = 0;
    for(int i = 0; i < n-1; ++i){
        int tmp = (int)(N[i]-'0');
        if(flag){
            ans += 9;
        }
        else if(tmp != 9){
            if(check(N , i)){
                flag = true;
                ans += tmp-1;
            }
            else{
                ans += tmp;
            }
        }
        else{
            ans += tmp;
        }
    }
    int las = (int)(N.back() - '0');
    if(flag){
        ans += 9;
    }
    else if(flag == false && las != 9){
        --ans;
        ans += 9;
    }
    else{
        ans += las;
    }

    cout << ans << endl;
    return;
}

int main() {
    #ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
    #else

    solve();

    #endif
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll INF=(ll)1e18+10;
const double PI=acos(-1);

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 (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

int ans[200010];
int mods[200010][2];

void calc_mods(int lim,int N,int type){
    mods[0][type]=1;
    if(N==0) return;
    for(int i=1;i<lim;++i){
        mods[i][type] = (mods[i-1][type]<<1)%N;
    }
}


int calc_val(string S,int type,int mod){
    int ret=0;
    if(mod==0) return 0;
    //reverse(S.begin(),S.end());
    for (int i = 0; i < S.length(); ++i) {
        if(S[i]=='1'){
            (ret+=mods[i][type])%=mod;
        }
    }
    return ret;
}

int calc(int a){
    if(a==0) return 0;
    int cnt=0;
    int tmp=a;
    while(a>0){
        if(a&1) ++cnt;
        a>>=1;
    }

    return calc(tmp%cnt)+1;
}

int main() {
    memset(ans,-1, sizeof(ans));
    int N; cin>>N;
    string S; cin>>S;
    int cnt_init=0;
    for(auto c:S){
        if(c=='1') ++cnt_init;
    }
    reverse(S.begin(),S.end());
    calc_mods(N,cnt_init-1,0);
    calc_mods(N,cnt_init+1,1);
    int val1_0 = calc_val(S,0,cnt_init-1);
    int val0_1 = calc_val(S,1,cnt_init+1);
    //cout<<val0_1<<endl;
    //return 0;
    vector<int> an;

    for (int i = 0; i < N; ++i) {
        if(S[i]=='1'){ //1to0
            int base=cnt_init-1;
            if(base==0){
                an.push_back(0);
                continue;
            }
            int val = (val1_0-mods[i][0]+base)%base;
            an.push_back(calc(val)+1);
        }else{
            int base=cnt_init+1;
            int val = (val0_1+mods[i][1])%base;
            //cout<<calc(val)+1<<endl;
            an.push_back(calc(val)+1);
        }
    }
    //cout<<"----"<<endl;
    for (int i = an.size()-1; i >= 0; --i) {
        cout<<an[i]<<endl;
    }

    return 0;
}


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

if N <= 9:
    print(N)
elif 10 <= N and N <= 99:
    print(9)
elif 100 <= N and N <= 999:
    print(9+N-100+1)
elif 1000 <= N and N <= 9999:
    print(9+900)
elif 10000 <= N and N <= 99999:
    print(9+900+N-10000+1)
else:
    print(9+900+90000)


Measured memory_bytes: 3060
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#define debug(x) cout<<x<<"\n";
#define Max(a,b) ((a)>(b)?(a):(b))
typedef long long ll;
const int N=1e5+10;
const ll inf=0x3f3f3f3f3f3f;
using namespace std;
ll arr[N];
int main()
{	
	ll x,n,cnt=0;
	while(cin>>n>>x)
	{
		for(int i=0;i<n;i++)
		cin>>arr[i];
		ll ans=0;
		if(arr[0]>x)
		{
			ans+=((arr[0]-x));
			arr[0]=x;	
		}
		for(int i=0;i<n;i++)
		{
			if(arr[i]+arr[i+1]>x)
			{
				ll temp=arr[i]+arr[i+1]-x;
				ans+=temp;
				if(arr[i+1]>=temp)
				arr[i+1]-=temp;
				else
				{
					arr[i+1]=0;
					//arr[i]-=(arr[i]-x);
				}
			}
		}
		//debug(arr[0]);debug(arr[1]);
		cout<<ans<<"\n";
	}
	return 0;
} 

Measured memory_bytes: 1024
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int X;
  cin>>X;
  int A=X/100, B=X%100;
  if(B%5==0) B /= 5;
  else B = B/5+1;
  if(A<B) cout<<0<<endl;
  else cout<<1<<endl;
}



Measured memory_bytes: 3608
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

bool comp(P x, P y) {
    return x.second < y.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vi v(n);
    bool same = true;
    rep(i, n) {
        cin >> v[i];
        if(v[0] != v[i]) same = false;
    }

    if(same) {
        cout << n/2 << endl;
        return 0;
    }

    map<int, int> od, ev;
    rep(i, n) {
        if(i&1) {
            od[v[i]]++;
        } else {
            ev[v[i]]++;
        }
    }

    vector<P> odp, evp;
    for(P x:od) {
        odp.emplace_back(x);
    }
    for(P x:ev) {
        evp.emplace_back(x);
    }

    sort(rall(odp), comp);
    sort(rall(evp), comp);

    int ans = INT_MAX;
    rep(i, min((int)odp.size(), 2)) {
        rep(j, min((int)evp.size(), 2)) {
            if(odp[i].first == evp[j].first) continue;
            ans = min(ans, n-odp[i].second-evp[j].second);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 9200
/*!enjoy karo yaar!*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

#include<bits/stdc++.h>
using namespace std;

#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)(x.size()))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     makep           make_pair
#define     maket           make_tuple
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)+(x)-1)/(x))
#define     gcd(a,b)        (__gcd((a),(b)))
#define     lcm(a,b)        ((a)*((b)/gcd((a),(b))))
#define     dbug(x)         cout<<#x<<": "<<(x)<<"\n"
#define     flush           fflush(stdout)
#define     show(x)         for(auto zz:x)cout<<zz<<" ";cout<<"\n";
#define     show2(x)        for(auto zz:x)cout<<zz.F<<" "<<zz.S<<"\n";

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const ld pi=acos(-1);
const ll inf=1e18,M=1e9+7;
const int N=1;

int h,w,n;

bool valid(int x,int y)
{
    return (1<=x && x+2<=h && 1<=y && y+2<=w);
}

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

void solve()
{
    cin>>h>>w>>n;

    map<pii,int> mp;

    int x,y;
    int a,b;
    for(int i=0;i<n;++i)
    {
        cin>>x>>y;

        for(int j=0;j<9;++j)
        {
            a=x+dx[j],b=y+dy[j];
            if(valid(a,b))
                ++mp[{a,b}];
        }
    }

    vi arr(10);

    arr[0]=(h-2)*(w-2)-sz(mp);
    for(auto c:mp)
        ++arr[c.S];
    for(auto c:arr)
        cout<<c<<"\n";
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    for(int z=1;z<=t;++z)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 56576
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int M,D;
    cin >> M >> D;
    int d_ten_max;

    int ans = 0;

    int m_tmp,d_tmp,d_tmp_ten,d_tmp_one;

    for(m_tmp = 1 ; m_tmp <= M ; m_tmp++ ){

        for(d_tmp = 10 ; d_tmp <= D ; d_tmp++ ){

            d_tmp_ten = d_tmp / 10;
            d_tmp_one = d_tmp % 10;

            if (d_tmp_one >= 2 && d_tmp_ten >= 2 && m_tmp == d_tmp_one * d_tmp_ten){
                ans++;
            }

        }
    }
    cout << ans << endl;
}

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

int calc(int x) {
    int sum = 0;
    while (x > 0) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    int ans;
    for (int i = 0; i <= N; i++) {
        int sum = calc(i);
        if (A <= sum && sum <= B) {
            ans += i;
        }
    }
    cout << ans << endl;
}


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

using namespace std;

int main(void) {
    string s, t;
    cin >> s >> t;

    vector<vector<long>> next(s.size(), vector<long>(26, -1));
    string ss = s + s;

    vector<long> latest(26, -1);
    for(int i=s.size()-1; i>=0; i--)
        latest[s[i]-'a'] = i + s.size();

    for(int i=s.size()-1; i>=0; i--) {
        for(int c=0; c<26; c++) {
            next[i][c] = latest[c];
        }
        latest[s[i]-'a'] = i;
    }


    long r = latest[t[0]-'a'];
    if(r == -1) {
        cout << r << endl;
        return 0;
    }

    for(int i=1; i<t.size(); i++) {
        long n = next[r%s.size()][t[i]-'a'];
        if(n == -1) {
            cout << -1 << endl;
            return 0;
        }
        r += n - (r%s.size());
    }
    cout << r+1 << endl;
}


Measured memory_bytes: 24832
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<iomanip>


#define MOD 1000000007
#define INF 1001001001
#define MIN -1001001001
#define rep(i,k,N) for(int i=k;i<N;i++)
#define MP make_pair
#define MT make_tuple //tie,make_tuple は別物
#define PB push_back
#define PF push_front
#define all(x) (x).begin(),(x).end()


using namespace std;
typedef long long ll;
typedef vector<ll> v;
typedef vector<vector<ll>> vv;

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

int main(){
    ll N,M;
    cin>>N>>M;
    vector<pair<ll,ll>> job(N);
    rep(i,0,N){
        ll a,b;
        cin>>a>>b;
        job[i] = MP(a,b);
    }
    sort(all(job));
    rep(i,0,N){
        swap(job[i].first,job[i].second);
    }
    int j = 0;

    priority_queue<pair<ll,ll>> jobs;
    ll ans = 0;

    rep(i,1,M+1){
        while(job[j].second == i){
            jobs.push(job[j]);
            j++;
        }
        if(!jobs.empty()){
            ans += jobs.top().first;
            jobs.pop();
        }
    }

    cout<<ans;
    return 0;
}

Measured memory_bytes: 3956
A, B, C, D = list(map(int, input().split()))
if A <= C:
    if B <= D:
        if B - C <= 0:
            print(0)
        else:
            print(B - C)
    else:
        if D - C <= 0:
            print(0)
        else:
            print(D - C)
else:
    if B <= D:
        if B - A <= 0:
            print(0)
        else:
            print(B - A)
    else:
        if D - A <= 0:
            print(0)
        else:
            print(D - A)

Measured memory_bytes: 8888
#include<bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define zero(v) memset(v,0,sizeof(v))
#define rep(i,n) for(int i=0;i<(n);i++)
#define foreach(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();it++)
#define all(v) (v).begin(),(v).end()
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
typedef long long ll;
typedef unsigned uint;
const int INF=0x3f3f3f3f;
const double EPS=1e-10;
typedef pair<int,int>P;
int inline in(){int x=0,c;for(;(uint)((c=getchar())-'0')>=10;)
{if(c=='-')return -in();if(!~c)throw ~0;}do{x=(x<<3)+(x<<1)+(c-'0');}
while((uint)((c=getchar())-'0')<10);return x;}
int main(){
	int A,B,C,D;
	cin>>A>>B>>C>>D;
	int Tn=(A-1)/D;
	int An=(C-1)/B;
	if(Tn<An){
		cout<<"No"<<endl;
	}else{
		cout<<"Yes"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3632
def solve(n, y):

    for i in range(n + 1):
        for j in range(n + 1):
            k = n - i - j
            if k < 0:
                continue
            if 10000 * i + 5000 * j + 1000 * k == y:
                return str(i) + " " + str(j) + " " + str(k)
    
    return "-1 -1 -1"

n, y = map(int, input().split())

print(solve(n, y))

Measured memory_bytes: 3060
import std.stdio, std.string;

void main(){
 auto s=readln.chomp;
 foreach(i;0..s.length-1)if(s[i]==s[i+1]){
writeln(i+1," ",i+2);
return;
}
foreach(i;0..s.length-2)if(s[i]==s[i+2]){
writeln(i+1," ",i+3);
return;
}
writeln("-1 -1");
}

Measured memory_bytes: 508
N, Q = map(int, input().split())
S = input()

cums = [0 for _ in range(N)]

s0 = None
cum = 0
for i,s in enumerate(S):
    s1 = s
    if s0=="A":
        if s1=="C":
            cum += 1
    s0 = s1
    cums[i] = cum

A = [0 for _ in range(Q)]
for i in range(Q):
    l, r = map(int, input().split())
    A[i] = cums[r-1]-cums[l-1]
for i in range(Q):
    print(A[i])



Measured memory_bytes: 53936
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
    freopen(name ".in","r",stdin); \
    freopen(name ".out","w",stdout); \
} while (0)
#endif

// }}}

const int N=11;
int n,m;
char s[N][N];
int main() {
    R(n,m);
    REP(i,n) R(s[i]);
    int x=0,y=0;
    while ( 1 ) {
        s[x][y]='.';
        if ( s[x+1][y]=='#' ) x++;
        else if ( s[x][y+1]=='#' ) y++;
        else break;
    }
    bool ok=1;
    REP(i,n) if ( strchr(s[i],'#') ) ok=0;
    W(ok?"Possible":"Impossible");
    return 0;
}


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

using namespace std;

typedef long long int ll;
typedef pair<int, int> P;
#define INF 10000000000000
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
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 main()
{
	string S;

	cin >> S;

	if (S == "Sunny")
		cout << "Cloudy" << endl;
	else if (S == "Cloudy")
		cout << "Rainy" << endl;
	else if (S == "Rainy")
		cout << "Sunny" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <limits.h>
#define N 100005

using namespace std;

int n;
int a[N], Min, Max;

inline void read(int &x) {
	x = 0; char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
}

int main() {
	read(n);
	Min = INT_MAX, Max = INT_MIN;
	for(int i = 1; i <= n; ++i)	{
		read(a[i]);
		Min = min(Min, a[i]);
		Max = max(Max ,a[i]);
	}
	if(Max - Min > 1) {
		puts("No");
	} else if(Max == Min) {
		if(Max == n - 1 || a[1] * 2 <= n) {
			puts("Yes");
		} else {
			puts("No");
		}
	} else {
		int cnt = 0;
		for(int i = 1; i <= n; ++i)
			if(a[i] == Max) ++cnt;
		if(Max - (n - cnt) > 0 && (Max - (n - cnt)) * 2 <= cnt) {
			puts("Yes");
		} else {
			puts("No");
		}
	}
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

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


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

const int MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void comb_init() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long comb(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll mod_pow(ll x, ll n, ll mod){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res * x % mod;//最下位ビットが立っているときにx^(2^i)をかける
        x = x * x % mod; //xを順次二乗していく
        n >>= 1;
    }
    return res;
}

//逆元を求める(フェルマーの小定理)X^(p-1)≡1 <=> X^(-1) ≡ X^(p-2) p:素数
ll mod_inv(ll x) {
    return mod_pow(x,MOD-2,MOD);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,a,b,c;
    cin>>n>>a>>b>>c;
    a = a * mod_inv(100) % MOD;
    b = b * mod_inv(100) % MOD;
    ll ret = 0;
    comb_init();
    REP(i,n){
        ll res = comb(n+i-1,i) * mod_pow(a,n,MOD) % MOD * mod_pow(b,i,MOD) % MOD * mod_pow(mod_pow(a+b,n+i,MOD),MOD-2,MOD) % MOD;
        ret += (n+i) * mod_pow(a+b,MOD-2,MOD) % MOD * res % MOD;
        ret %= MOD;
    }
    REP(i,n){
        ll res = comb(n+i-1,i) * mod_pow(b,n,MOD) % MOD * mod_pow(a,i,MOD) % MOD * mod_pow(mod_pow(a+b,n+i,MOD),MOD-2,MOD) % MOD;
        ret += (n+i) * mod_pow(a+b,MOD-2,MOD) % MOD * res % MOD;
        ret %= MOD;
    }
    cout<<ret<<endl;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int q;
    cin >> q;

    int muki = 1;
    string t = "";
    for(int i=0; i<q; i++)
    {
        int x;
        cin >> x;
        if(x==1) muki *= -1;
        else
        {
            int f;
            cin >> f;
            char c;
            cin >> c;
            if(f==1 && muki==1) t.push_back(c);
            else if(f==1 && muki==-1) s.push_back(c);
            else if(f==2 && muki==1) s.push_back(c);
            else if(f==2 && muki==-1) t.push_back(c);
        }
    }

    if(muki==1)
    {
        reverse(t.begin(), t.end());
        cout << t << s << endl;
    }
    else
    {
        reverse(s.begin(), s.end());
        cout << s << t << endl;
    }
    

    

    return 0;
}


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

using namespace std;
using ll = long long;
using ii = pair<int, int>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

ll solve(int N, const vector<ll>& xs)
{
    return 0;
}

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

    int A, B;
    cin >> A >> B;

    switch (A + B) {
    case 3:
        cout << 3 << endl;
        break;

    case 4:
        cout << 2 << endl;
        break;

    default:
        cout << 1 << endl;
    };

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>

using namespace std;
typedef long long ll;

int gcd(int x, int y) {
  if (x < y) swap(x, y);
  while (y > 0) {
    int r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//for(int i = ; i < ; i++){}

int main(){
    int n;
    cin>>n;
    int a[n];
    vector <int> l1;
    for(int i = 0;i<n;i++){
        cin>>a[i];
    }
    bool f=true;
    int min = 0;
    for(int i = 0;i<n-1;i++){
        if(a[i]<a[i+1]&&f == false) {
            f = true;
            min=a[i];
        }
        if(a[i]>a[i+1]&&f == true){
            f = false;
            l1.push_back(a[i]-min);
            min=0;
            }
    }
    if(a[n-2]<a[n-1]) l1.push_back(a[n-1]-min);
    if(a[n-2]==a[n-1]&&f==true) l1.push_back(a[n-2]-min);
    int sum=0;
    for(int i = 0; i<l1.size(); i++)sum+=l1[i];
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
N, K = list(map(int,input().split()))
A = list(map(int,input().split()))
P = [0] + [abs(i) for i in A if i> 0 ]
M = [abs(i) for i in A if i< 0 ] +[0]
M = sorted(M,reverse =False)


cnt = 10000000000

if len(P) == len(M) == 1:
    cnt = 0
elif len(P) == 1:
    cnt = M[K]
elif len(M) == 1:
    cnt = P[K]
else:
    #リストがK以下の場合不具合が起きる
    #for i in range(1,K):   
    #len(P)=4 len(M)=3 K=5の場合、IndexErrorとなる。rangeをうまく設定する必要があるが実装できない。
    #正の方向でi個ろうそくを通って、負の方向にK-i個ろうそくを通る
    s = max(0,K-len(M)+1)
    e = min(K+1, len(P))
    for i in range(s, e):
        cnt =min(cnt,P[i]*2 + M[K-i])
    #負の方向でi個ろうそくを通って、正の方向にK-i個ろうそくを通る
    s1 = max(0,K-len(P)+1)
    e1 = min(K+1, len(M))
    for i in range(s1, e1):
        cnt =min(cnt,M[i]*2 + P[K-i])

print(cnt)

Measured memory_bytes: 15076
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma comment(linker, "/STACK:1024000000")
#pragma warning( disable : 6031)
#pragma warning( disable : 4244)
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdint>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <numeric>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <sstream>
#include <functional>
#include <iomanip>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <chrono>

#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define eps (1e-15)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<double> vd;
typedef vector< vd > vvd;
typedef vector< string > vs;
typedef pair< int, int > pii;
typedef vector< pii > vpii;
typedef vector<ll> vll;
typedef vector<vector<long long>> vvll;
typedef tuple<int, int, int> tiii;
const long long mod = int(1e9) + 7;
const double eps9 = 1e-9;



int main() {
#ifdef LOCAL_MACHINE
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
#endif
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << setprecision(18) << fixed;
	int n, m;
	cin >> n >> m;
	vs a(n);
	for (auto& x : a)
		cin >> x;
	vvi score(n, vi(m, 1e9));
	queue<pair<pii, int>> q;
	
	int dx[] = { 1, 0 };
	int dy[] = { 0, 1 };
	score[0][0] = 0;
	if (a[0][0] == '#')
		score[0][0] = 1;
	q.push({ {0, 0}, score[0][0] });
	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();
		int cs = cur.second;
		int x = cur.first.first, y = cur.first.second;

		for (int d = 0; d < 2; d++)
		{
			int cx = x + dx[d], cy = y + dy[d];
			if (cx < 0 || cy < 0 || cx >= n || cy >= m)
				continue;
			int ns = cs;
			if (a[x][y] == '.' && a[cx][cy] == '#')
				ns++;
			if (score[cx][cy] <= ns)
				continue;
			score[cx][cy] = ns;
			q.push({ {cx, cy}, ns });
		}

	}
	cout << score[n - 1][m - 1];
	return 0;

}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define arep(i,x,n) for(int i=int(x);i<(int)(n);i++)
#define rep(i,n) for(long long i = 0;i < n;++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9+7  
using ll = long long; 
using P=pair<int,int>;
using lP=pair<ll,ll>;
using fP=pair<double,double>;


int main(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    char c;
    if(s[0]=='L')c='R';
    else c='L';
    int a=0;
    rep(i,n){
        if(i==0)continue;
        if(s[i]!=s[i-1])a++;
    }
    int ans=0;
    if(a+1<=2*k){
        ans=s.size()-1;
    }
    else{
        ans=s.size()-(a+1)+2*k;
    }
    cout<<ans<<endl;
}

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

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

    int ans = 0;
    int ansCount = 0;

    for(int i = 1; i <= N; i++)
    {
        int count = 0;
        int tmp = i;
        
        while(tmp % 2 == 0)
        {
            tmp /= 2;
            count++;
        }

        if(ansCount <= count)
        {
            ansCount = count;
            ans = i;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15
from itertools import accumulate

def main():
    N = int(input())
    A = list(map(int,input().split()))
    cumsum = list(accumulate([0] + A))
    ans = INF
    l = 0
    r = 2
    fl = lambda i,l:abs(cumsum[i + 1] - 2*cumsum[l + 1])
    fr = lambda i,r:abs(cumsum[-1] - cumsum[i + 1] - 2*(cumsum[r + 1] - cumsum[i + 1]))

    for i in range(1,N - 2):
        while fl(i,l + 1) < fl(i,l):
            l += 1
        while fr(i,r + 1) < fr(i,r):
            r += 1
        a = cumsum[l + 1]
        b = cumsum[i + 1] - a
        c = cumsum[r + 1] - a - b
        d = cumsum[-1] - a - b - c
        ans = min(ans,max(a,b,c,d) - min(a,b,c,d))
    print(ans)
    
if __name__ == '__main__':
    main()

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

int main(){
  int D; cin >> D;
  vector<int> c(26);
  for(int i=0; i<26; i++) cin >> c[i];
  vector<vector<int>> s(D,vector<int>(26));
  for(int i=0; i<D; i++){
    for(int j=0; j<26; j++){
      cin >> s[i][j];
    }
  }
  vector<int> lastc(26,-1);
  
  int sat=0;
  for(int i=0; i<D; i++){
    int t; cin >> t;
    t--;
    sat+=s[i][t];
    lastc[t]=i;
    int degrade=0;
    for(int j=0; j<26; j++){
      degrade+=c[j]*(i-lastc[j]);
    }
    sat-=degrade;
    cout << sat << endl;
  }
}

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

namespace ConsoleApp62 {
    class Program {
        static void Main(string[] args) {
            var st = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int H = st[0];
            int W = st[1];

            var array = new char[H, W];

            for (int i = 0; i < H; i++) {
                string X = Console.ReadLine();
                for (int j = 0; j < W; j++) {
                    array[i, j] = X[j];
                }
            }

            //全て点の数値を記録
            var yoko = Enumerable.Repeat(0, H).ToArray();
            var tate = Enumerable.Repeat(0, W).ToArray();

            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (array[i, j] == '#') {
                        yoko[i] = 1;
                        break;
                    }
                }
            }

            for (int j = 0; j < W; j++) {
                for (int i = 0; i < H; i++) {
                    if (array[i, j] == '#') {
                        tate[j] = 1;
                        break;
                    }
                }
            }

            int yoko_skip = yoko.Where(x => x == 0).Count();
            int tate_skip = tate.Where(x => x == 0).Count();

            //Console.WriteLine(yoko_skip);
            //Console.WriteLine(tate_skip);

            var ans = new char[H - yoko_skip, W - tate_skip];

            int ans_yoko = 0;
            int ans_tate = 0;

            for (int i = 0; i < H; i++) {
                ans_tate = 0;
                if (yoko[i] == 0) {
                    continue;
                }
                for (int j = 0; j < W; j++) {
                    if (tate[j] == 0) {
                        continue;
                    }

                    ans[ans_yoko, ans_tate] = array[i, j];
                    ans_tate++;
                }

                ans_yoko++;
            }

            for (int i = 0; i < H - yoko_skip; i++) {
                for (int j = 0; j < W - tate_skip; j++) {

                    Console.Write(ans[i, j]);
                }
                Console.WriteLine();
            }

        }
    }
}

Measured memory_bytes: 13476
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

int n, a[30][30];
int dp[1 << 21];
bool vis[1 << 21];

int solve(int x)
{
    if (vis[x])
        return dp[x];
    vis[x] = true;
    int cnt = 0;
    rep(i, n) if (!(x & (1 << i))) cnt++;
    if (cnt == n)
        return dp[x] = 1;
    int res = 0;
    rep(i, n) if ((x & (1 << i)) && a[cnt][i])
        res = (res + solve(x - (1 << i))) % mod;
    return dp[x] = res;
}

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

    cin >> n;
    rep(i, n) rep(j, n) cin >> a[i][j];
    cout << solve((1 << n) - 1) << endl;
}

Measured memory_bytes: 18688
#include<iostream>
#include<vector>
using namespace std;
int N,M;
string t[2000];
string u[2000];
 
bool check(string &a,string &b,int x){
  string tmp=a+b;
  for(int i=0;i<16;i++){
    if(u[x][i]=='?')continue;
    if(u[x][i]!=tmp[i])return false;
  }
  return true;
}
 
struct data {string a,b,c;};
vector<data> ans;
 
int main(){
  string str,str2,str3;
  while(cin>>N>>M && (N||M)){
    ans.clear();
    for(int i=0;i<N;i++){
      cin>>t[i]>>str>>str2;
      u[i]=str+str2;
    }
    for(int i=0;i<M;i++){
      cin>>str>>str2>>str3;
      bool flg=false;
      for(int j=0;j<N;j++){
    if(check(str,str2,j)){
      if(t[j]=="permit")flg=true;
      else flg=false;
    }
      }
      if(flg)ans.push_back( (data){str,str2,str3} );
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<(int)ans.size();i++){
      cout<<ans[i].a<<" "<<ans[i].b<<" "<<ans[i].c<<endl;
    }
  }
  return 0;
}

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

int N, A, B;
int dist[2005];
bitset<2005> vis;
set<tuple<int, int, int>> lol;
vector<int> adj[2005];
int ans[2005];

void check(int u, int v, int di) {
    if(v > u) swap(u, v);
    if(!lol.count(make_tuple(u, v, di))) {
        lol.insert(make_tuple(u, v, di));
        ans[di]++;
    }
}

void BFS(int ao) {
    queue<int> q;
    q.push(ao);
    vis = 0;
    vis[ao] = 1;
    dist[ao] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int v : adj[u]) {
            if(vis[v]) continue;
            vis[v] = 1;
            dist[v] = dist[u] + 1;
            check(ao, v, dist[v]);
            q.push(v);
        }
    }
}

int main() {
    cin >> N >> A >> B;
    for(int i = 2; i <= N; i++) {
        adj[i].push_back(i-1);
        adj[i-1].push_back(i);
    }
    adj[A].push_back(B);
    adj[B].push_back(A);
    for(int i = 1; i <= N; i++) BFS(i);
    for(int i = 1; i <+ N; i++) cout << ans[i] << "\n";
}

Measured memory_bytes: 125696
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
a = [STR() for _ in range(n)]
b = [STR() for _ in range(m)]
for i in range(n - m + 1):
    for j in range(n - m + 1):
        flag = True
        for k in range(m):
            if a[i + k][j:j + m] != b[k]:
                flag = False
                break
        if flag:
            print('Yes')
            exit()
print('No')


Measured memory_bytes: 5192
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
int32_t main()
{
    string s,t;
    cin>>s>>t;
    int n,m,i,j;
    n=s.size();
    m=t.size();
    vector<vector<int> > dp(n+1,vector<int> (m+1));
    string ans="";
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(s[i-1]==t[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }


    int x=n,y=m;
    while(x!=0 && y!=0)
    {
        if(dp[x-1][y]==dp[x][y])
            x--;
        else if(dp[x][y]==dp[x][y-1])
            y--;
        else
        {
            ans+=s[x-1];
            x--;
            y--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout<<ans;
    return 0;
}


Measured memory_bytes: 73628
using System;

namespace ARC085_D___ABS
{
    class Program
    {
        static void Main(string[] args)
        {
            var NZW = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
            var Ai = Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
            Console.WriteLine(NZW[0] != 1 ? Math.Max(Math.Abs(Ai[Ai.Length - 1] - Ai[Ai.Length - 2]), Math.Abs(NZW[2] - Ai[Ai.Length - 1])) : Math.Abs(NZW[2] - Ai[0]));
        }
    }
}


Measured memory_bytes: 13208
A, B, C = map(int, input().split())
if A % 2 == 0 and A == B and B == C:
    print(-1)
    exit()

count = 0
while (A % 2, B % 2, C % 2) == (0, 0, 0):
    A, B, C = (B + C) // 2, (A + C) // 2, (A + B) // 2
    count += 1

print(count)


Measured memory_bytes: 38256
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

multiset<long long> vals;

int n;

long long mMax = 0, mMin = (1 << 30) - 1;

vector<pair<long long, long long>> s;

long long curProd(int removed) {
  return (max(mMax, s[s.size() - 1].first) - min(mMin, s[removed].first)) * ((*(--vals.end())) - (*vals.begin()));
}

int main() {
  cin >> n;

  for (int i = 1 ; i <= n; ++i) {
    long long x, y;
    cin >> x >> y;
    if (x < y)
      swap(x, y);
    vals.insert(x);
    s.push_back(make_pair(y, x));
  }

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

  long long bestProd = curProd(0);

  for (int removed = 0; removed < n; ++removed) {
    vals.insert(s[removed].first);
    mMin = min(mMin, s[removed].second);
    mMax = max(mMax, s[removed].second);
    bestProd = min(bestProd, curProd(removed + 1));
  }

  cout << bestProd;
  return 0;
}


Measured memory_bytes: 22892
n, m = map(int, input().split())
boxes = [[0, 1] for _ in range(n)]
boxes[0][0] = 1
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    boxes[x][1] -= 1
    boxes[y][1] += 1
    if boxes[x][0] == 1:
        boxes[y][0] = 1
    else:
        if boxes[y][0] == 1:
            continue
        else:
            boxes[y][0] = 0  
    if boxes[x][1] == 0:
        boxes[x][0] = -1
ans = 0
for a, b in boxes:
    # print(a, b)
    if a > 0:
        ans += 1
# print(boxes)
print(ans)


Measured memory_bytes: 13172
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr long long MOD = 1000000007;
constexpr long long INF = 1LL << 60;
const long double PI = acosl(-1.0);
constexpr long double EPS = 1e-11;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main(){
    ll n, k;
    cin >> n >> k;
    ll x[n];
    ll ans = INF;
    for (ll i = 0; i < n; i++) cin >> x[i];
    for (ll i = 0; i < n - k+1; i++){
        ans = min(ans, min(abs(x[i]) + x[i + k - 1] - x[i], abs(x[i + k - 1]) + x[i + k - 1] - x[i]));
    }
    cout << ans << endl;
}

Measured memory_bytes: 4412
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const long long INF = 1e15;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    int h,w;
    cin >> h >> w;

    int sx,sy,gx,gy;
    cin >> sy >> sx >> gy >> gx;
    sx--;sy--;gx--;gy--;

    string sur[h];

    for(int i = 0; i < h; i++) cin >> sur[i];
    queue<pair<int,int>> p,q;

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

    p.push(make_pair(sx,sy));

    int can = 0;

    while(!p.empty()){
        while(!p.empty()){
            pair<int,int> now = p.front();
            p.pop();
            q.push(now);
            for(int i = 0; i < 4; i++){
                pair<int,int> nxt = make_pair(now.first+dx[i],now.second+dy[i]);
                if(0 <= nxt.first && nxt.first < w && 0 <= nxt.second && nxt.second < h){
                    if(sur[nxt.second][nxt.first] == '.'){
                        if(nxt == make_pair(gx,gy)){
                            cout << can << endl;
                            return 0;
                        }
                        p.push(nxt);
                        sur[nxt.second][nxt.first] = '#';
                    }
                }
            }
        }
        can++;
        while(!q.empty()){
            pair<int,int> now = q.front();
            q.pop();
            for(int i = -2; i < 3; i++){
                for(int j = -2; j < 3; j++){
                    pair<int,int> nxt = make_pair(now.first+i,now.second+j);
                    if(0 <= nxt.first && nxt.first < w && 0 <= nxt.second && nxt.second < h){
                        if(sur[nxt.second][nxt.first] == '.'){
                            if(nxt == make_pair(gx,gy)){
                                cout << can << endl;
                                return 0;
                            }
                            p.push(nxt);
                            sur[nxt.second][nxt.first] = '#';
                        }
                    }
                }
            }
        }
    }

    cout << -1 << endl;
    return 0;
}


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

int main(void){
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  printf("%c%c%c\n", s1[0] - 'a' + 'A', s2[0] - 'a' + 'A', s3[0] - 'a' + 'A');
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
#ABC48 C

n,x = map(int,input().split())
a = list(map(int,input().split()))

b = a.copy()
if a[0] > x:
    b[0] = x
for i in range(n-1):
    if b[i] + b[i+1] > x:
        b[i+1] -= (b[i]+b[i+1] - x)
        if b[i+1] < 0:
            b[i] -= abs(b[i+1])
            b[i+1] += abs(b[i+1])
ans = 0
for i in range(n):
    ans += abs(b[i] - a[i])
print(ans)


Measured memory_bytes: 14432