akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
const int N=1e9+7;
#define int long long
#define double long double

int32_t main()
{
  #ifndef ONLINE_JUDGE
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
  #endif
 IOS;
 string a,b;
 cin>>a>>b;
 int p=a.size();
 int q=b.size();
 int ans=0;
 for (int i = 0; i < p-q+1; ++i)
 {
 	int c=0,d=0;
 	for (int j = i; j < i+q&&c<q; ++j)
 	{
 		/* code */if(a[j]==b[c])
 		{
 					d++;
 				}
 					c++;
 	}
 	ans=max(ans,d);
 }
 cout<<q-ans;

 	



  
 




  
return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> P;

int main() {
  int q;
  cin>>q;
  vector<bool> a(100005,true);
  a[1]=false;
  for (int i=2; i<100000; i++) {
    if (a.at(i)==false) continue;
    for (int j=i*2; j<=100000; j+=i) {
      a.at(j)=false;
    }
  }
  vector<int> sum(100005);
  sum[0]=0;
  for (int i=2; i<=100000; i++) {
    if (a[i]&&a[(i+1)/2]) sum[i]=sum[i-1]+1;
    else sum[i]=sum[i-1];
  }
  for (int i=0; i<q; i++) {
    int l,r;
    cin>>l>>r;
    cout<<sum[r]-sum[l-1]<<endl;
  }
  return 0;
}

Measured memory_bytes: 1024
/*
          , -- 、
        /;;;;;;', 　　　
        i二二二i
      , ' 　    ヽ ???
     i　ﾉﾉﾉﾉﾉﾍ .', 　　
     〉ﾘi' ﾟ ヮﾟﾉﾚく　 WAyon..........
  ○⊂}〈lﾄ--ｲl〉{つ● 　　
      ,ｒ/ー i-ヽヽ 　　　
     ｀｀i_ﾗi_ﾗ
*/

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
const int INF=(int)1e12;
const int mod=(int)1e9+7;
#define all(a) (a).begin(),(a).end()
typedef vector<vector<int>> graph;

#define pb push_back

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

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

signed main() {
    int n,m;cin >>n>>m;
    vector<int> a(m);int cnt=0;
    rep(i,m){
        cin>>a[i];cnt+=a[i];
    }
    if(n-cnt>=0)cout <<n-cnt<<endl;
    else cout <<-1<<endl;

}

















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

// macros
#define int long long 
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define all(c) c.begin(), c.end()
#define PB push_back
#define MP make_pair
#define bitcount __builtin_popcount
#define watch(x) cerr<< (#x) << " is " << (x) <<"\n";
#define sz(x) ((int)((x).size()))
#define UNIQUE(c) (c).resize(unique(all(c)) - (c).begin())
#define pii2ll(p) ((ll)(p).first<<32 | (p).second)

// type definitions
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< vi > vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef long double ld;

// template functions
template < typename A, typename B >
ostream& operator << ( ostream& os, const pair< A, B > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}
template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "[";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}
template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "{";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}
template < typename A, typename B >
ostream &operator << ( ostream & os, const map< A, B > &v ) {
    os << "[";
    typename map< A, B >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " -> " << it -> second ;
    }
    return os << "]";
}
template <typename T>
inline void printV(vector<T>& a, int n) { for(int i=0; i<n; i++) { cerr<<a[i]<<" "; } cerr<<"\n"; }
template <typename T>
inline void printVV(vector<vector<T>>& a) { for(int i=0; i<sz(a); i++) { cerr<<a[i]<<"\n"; } cerr<<"\n"; }
template <typename T>
inline void clearVV(vector<vector<T>>& a) { for(auto &x : a) { x.clear(); } a.clear(); }
template <typename T>
inline void assignVV(vector<vector<T>> &a, T val) { for(int i=0; i<sz(a); i++) { a[i].assign(sz(a[i]), val); } }
template<typename T>
T gcd(T a, T b) { if(a==0 or b==0) return a+b; return gcd(b, a%b) ; }

// random number generation
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// constants
const long double eps = LDBL_EPSILON;
const int inf = 5e8;
const int modn = 1e9+7;
const int MAX = 1e5;


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // Your code here
	int p, q, r;
	cin>>p>>q>>r;
	int ans = min(p+q, min(p+r, r+q));
	cout<<ans<<"\n";
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>

using namespace std;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    long long N, M; cin >> N >> M;
    vector<int> A(M), B(M);
    for (int i = 0; i < M; ++i) {
        cin >> A[i] >> B[i], --A[i], --B[i];
    }
        
    UnionFind uf(N);
    long long cur = N * (N-1) / 2;
    vector<long long> res;
    for (int i = 0; i < M; ++i) {
        res.push_back(cur);
            
        int a = A[M-1-i], b = B[M-1-i];
        if (uf.issame(a, b)) continue;
        
        long long sa = uf.size(a), sb = uf.size(b);
        cur -= sa * sb;
        uf.merge(a, b);
    }
        
    reverse(res.begin(), res.end());
    for (int i = 0; i < res.size(); ++i) cout << res[i] <<endl;
}

Measured memory_bytes: 3444
#include <algorithm>

#include <bitset>

#include <tuple>

#include <cstdint>

#include <cstdio>

#include <cctype>

#include <assert.h>

#include <stdlib.h>

#include <stdio.h>

#include <cassert>

#include <cfloat>

#include <climits>

#include <cmath>

#include <complex>

#include <ctime>

#include <deque>

#include <fstream>

#include <functional>

#include <iomanip>

#include <iostream>

#include <iterator>

#include <list>

#include <limits>

#include <map>

#include <memory>

#include <queue>

#include <random>

#include <set>

#include <stack>

#include <string>

#include <unordered_map>

#include <unordered_set>

#include <utility>

#include <vector>

#include <math.h>
using namespace std;
int main() {
    int S, W;
    cin >> S >> W;
    if (S <= W) {
        cout << "unsafe" << endl;
    }
    else {
        cout << "safe" << endl;
    }
}
  
        

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long int i=0,j,c=0,saidai=0,m,n,a,b;
    cin >> a >> b;
    m=b-a-1;
    cout << m*(m+1)/2-a << endl;
    return 0;

}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
	while(cin>>n>>m){
		int sum=0;
		for(int i=1;i<=n-1;i++){
			sum+=i;
		}
		for(int i=1;i<=m-1;i++){
			sum+=i;
		}
		cout<<sum<<endl;
	}
}

Measured memory_bytes: 256
def main():
    N = int(input())
    A = [int(i) for i in input().split()]

    def gcd(x, y):
        if y == 0:
            return x
        while y != 0:
            x, y = y, x % y
        return x

    L = [0] * (N+1)
    R = [0] * (N+1)
    for i in range(N):
        L[i+1] = gcd(L[i], A[i])
        R[-(i+2)] = gcd(R[-(i+1)], A[-(i+1)])
    ans = 0
    # print(L)
    # print(R)
    for i in range(1, N+1):
        ans = max(ans, gcd(L[i-1], R[i]))
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 63984
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

int n;
double a, b, c;
char ans;

int main(){
	while (cin >> n&&n){
		REP(i, n){
			cin >> a >> b >> c;
			if (a == 100 || b == 100 || c == 100 ||
				(a + b) / 2 >= 90 || (a + b + c) / 3 >= 80){
				ans = 'A';
			}
			else if ((a + b + c) / 3 >= 70 
				|| ((a >= 80 || b >= 80) && (a + b + c) / 3 >= 50)){
				ans = 'B';
			}
			else ans = 'C';
			cout << ans << endl;
		}
	}
}

Measured memory_bytes: 1220
import std.stdio;
import std.string;
import std.conv;
void main(){
	int[101] counter; 
	string rc;
	int max;
	while( 1 ){
		rc = readln().chomp();
		if( !rc ){	break;	}
		counter[ to!int( rc ) ]++;
		if( max < counter[ to!int( rc ) ] ){
			max = counter[ to!int( rc ) ];
		}
	}
	foreach( i,c ; counter ){
		if( c == max ){
			writeln( i );
		}
	}
}

Measured memory_bytes: 1044
n = gets.to_s.to_i
a = gets.to_s.split.map{|t| t.to_i }

s = 1
ans = 0

remain_folia = a.sum

a.each do |f, i|
  if f > s
    puts -1
    exit
  end
  ans += s
  remain_folia -= f
  s = [(s-f) * 2, remain_folia].min
end

puts ans

Measured memory_bytes: 20716
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;
constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

constexpr int N = 5009;

ll n, a, b, p[N], dp[N];

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

    cin >> n >> a >> b;
    rep(i, n) cin >> p[i];
    fill(ALL(dp), inf);
    dp[0] = 0;
    rep(i, n) {
        ll x = *min_element(dp, dp + p[i]);
        dp[p[i]] = x;
        rep(j, p[i]) dp[j] += a;
        FOR(j, p[i] + 1, n + 1) dp[j] += b;
    }
    cout << *min_element(dp, dp + n + 1) << endl;

    return 0;
}

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

#define whatis(x) cerr << #x << ": " << x << endl;

const long long N = 1e3+1, M = 1e9+7;
bool a[N][N];
long long h, w, dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> h >> w;
    for (long long i = 1; i <= h; i++) {
        string s;
        cin >> s;
        for (long long j = 0; j < w; j++) {
            if (s[j] == '#') {
                a[i][j+1] = 1;
            }
        }
    }
    dp[1][1] = 1;
    for (long long i = 1; i <= h; i++) {
        for (long long j = 1; j <= w; j++) {
            if (a[i][j] || (i == 1 && j == 1)) continue;
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % M;
        }
    }
    cout << dp[h][w] << endl;
    return 0;
}


Measured memory_bytes: 9088
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

int h,w,dp[110][110];
char c[110][110];

signed main()
{
	ios::sync_with_stdio(false);
	cin>>h>>w;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>c[i][j];
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(i==1&&j==1) dp[i][j]=0;
			else if(i==1){
				dp[i][j]=dp[i][j-1]+(c[i][j]=='.'&&c[i][j-1]=='#');
			}
			else if(j==1){
				dp[i][j]=dp[i-1][j]+(c[i][j]=='.'&&c[i-1][j]=='#');
			}
			else{
				dp[i][j]=min(dp[i][j-1]+(c[i][j]=='.'&&c[i][j-1]=='#'),dp[i-1][j]+(c[i][j]=='.'&&c[i-1][j]=='#'));
			}
		}
	}
	cout<<dp[h][w]+(c[h][w]=='#')<<endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define res register int
using namespace std;

inline int read()
{
	char ch=getchar();
	int x=0,f=0;
	while(ch<'0'||ch>'9')
	{
		f|=ch=='-';
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f?-x:x;
}
int n,x;
int a[2005],minx[2005][2005];
int main()
{
	n=read(),x=read();
	for(int i=1;i<=n;i++)
	a[i]=read();
	memset(minx,127,sizeof minx);
	long long ans=((long long)1<<61);
	for(int i=1;i<=n;i++)
	{
		minx[i][0]=a[i];
		for(int j=1;j<=n;j++)
		minx[i][j]=min(minx[i][j-1],a[(i-j-1+n)%n+1]);
	}
	for(int i=0;i<=n;i++)
	{
		long long sum=0;
		for(int j=1;j<=n;j++)
		sum+=minx[j][i];
		sum+=(long long)i*x;
		ans=min(ans,sum);
	}
	printf("%lld\n",ans);
}

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

#define INF 10000000

struct edge {int from,to,cost;};

edge es[2000];

int d[1000];
int v,e;

/*
bool find_negative_loop(){
    fill(d,d+1000,0);

    for(int i=0;i<v;i++){
        for(int j=0; j<e; j++){
            edge ed = es[j];
            if(d[ed.to] > d[ed.from] + ed.cost){
                d[ed.to] = d[ed.from] + ed.cost;

                if(i == v-1) return true;
            }
        }
    }
    return false;
}*/

bool shortest_path(int s){
    for(int i=0; i<v; i++){
        d[i] = INF;
    }
    d[s] = 0;
    int count = 0;
    while(1){
        if(count > v){
            return true;
        }
        bool update = false;
        for(int i=0; i<e; i++){
            edge ed = es[i];
            if(d[ed.from] != INF && d[ed.to] > d[ed.from] + ed.cost){
                d[ed.to] = d[ed.from] + ed.cost;
                update = true;
            }
        }
        if(!update) break;
        count++;
    }
    return false;
}

int main(){

    int r,s,t,dd;

    cin >> v >> e >> r;

    for(int i=0; i<e; i++){
        cin >> s >> t >> dd;
        es[i].to = t;
        es[i].from = s;
        es[i].cost = dd;
    }

    if(shortest_path(r)){
        cout << "NEGATIVE CYCLE" << endl;
    }
    else{
        for(int i=0;i<v;i++){
            if(d[i] == INF){
                cout << "INF" << endl;
            }
            else{
                cout << d[i] << endl;
            }
        }
    }

    return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<int > V(N),C(N);
  for(int i=0; i<N; i++){
    cin >> V[i];
  }
  for(int i=0; i<N; i++){
    cin >> C[i];
  }
  vector<int > Diff(N);
  for(int i=0; i<N; i++){
    Diff[i] = V[i]-C[i];
  }
  sort(Diff.begin(), Diff.end());
  int ans = 0;
  for(int i=0; i<N; i++){
    if(Diff[i]>0){
      ans+=Diff[i];
    }
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

#define int long long

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a, s;
    
    cin >> a >> s;

    int sum = 0;
    int mi = 10000000;
    
    int d;
    
    for(int i = 0; i < a; ++i)
    {
        cin >> d;
        
        s -= d;
        mi = min(mi, d);
    }
    
    cout << a + (s / mi) << endl;

    return 0;
}



Measured memory_bytes: 256
//e4 - e5 - f4
//#include <boost/multiprecision/cpp_int.hpp> 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
typedef long long int ll;
typedef double db;
// __int128 s128;
// __uint128_t u128;
typedef unsigned long long u64;
#define int long long int
#define P 1000000007
#define Q 1000000006
#define sz(a) (ll)a.size()
#define lt(a) (ll)a.length()
#define pll pair<ll,ll>
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define bac(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define umll unordered_map<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define mt make_tuple
#define eb emplace_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define teevra_gati ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define N 100005
#define PI 3.14159265359
#define inf LLONG_MAX
//using namespace boost::multiprecision; 
using namespace __gnu_pbds;
using namespace std;

void solve(){
    ll x;
    mll m;
    f(i,0,5) {cin>>x; m[x]++;}
    f(i,1,6) if(m.count(i)==0) {cout<<i<<endl; return;}
}

signed main() {
    teevra_gati
    
    
    solve();

    return 0;
}

Measured memory_bytes: 3656
N, K = map(int, input().split())
A = list(map(int, input().split()))

from itertools import groupby, accumulate, product, permutations, combinations

def solve(N,K,A):
    mod = 10**9+7
    dp = [[0]*(K+1) for _ in range(N+1)] #dp[i][j] i人目まででj個を分ける場合の数
    dp[0][0] = 1
    for i in range(1,N+1):
        cum = list(map(lambda x:x%mod,accumulate(dp[i-1])))
        for j in range(K+1):
            dp[i][j] = cum[j]
            k = j-A[i-1]
            if k>0:
                dp[i][j] -= cum[k-1]
    ans = dp[N][K]%mod
    return ans
print(solve(N,K,A))

Measured memory_bytes: 175624
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;


const ll MOD = 1e9+7;


signed main(){
    ll n;
    cin >> n;
    ll a[n],b[n];
    rep(i,0,n){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(a,a+n);
    ll r = a[n/2],l = a[n/2-1];
    rep(i,0,n){
        if(b[i] <= l){
            cout << r << endl;
        }
        else{
            cout << l << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 6696
M,D =  map(int,input().split())
count = 0
for i in range(1,M+1):
    for j in range(1,D+1):
        d1 = j//10
        d10 = j%10
        if d1*d10==i and d1>=2 and d10 >= 2:
            count += 1
print(count)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
 execution in cmd of windows:
 
 
  g++ p1.cpp -o p1
  
  
  p1
 
 */
typedef double dd;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define nl <<"\n"
#define con continue
#define br break
#define vll vector<ll>
#define vpll vector<pair<ll,ll> >
ll mx=INT_MAX;
ll mi=INT_MIN;
#define mem0(a)         memset(a,0,sizeof(a))
#define mem1(a)         memset(a,-1,sizeof(a))
#define all(v) v.begin(), v.end()
#define fsort(v) sort(all(v))  
#define rsort(v) sort(v.rbegin(),v.rend())
#define rev(v) reverse(all(v))
#define maxc(v) max_element(all(v))
#define minc(v) min_element(all(v))
#define sumv(v,x) accumulate(v.begin(),v.end(),x);
const ll mod = 998244353;
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
#define io { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define cer cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
#define cs ll t;cin>>t;while(t--)


int main()
{
        io;
        //////////////////////////////////
        
        ll n,i,j,s=0;
        cin>>n;
        if(n%1000==0) cout<<0;
        else
        {
        	cout<<(n/1000+1)*1000-n;
        }
    	//////////////////////////////////
        cer;
}


Measured memory_bytes: 3800
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define si(n) scanf("%d",&n);
#define PI acos(-1.0)
#define sl(n) scanf("%lld",&n);
#define sf(n) scanf("%lf",&n);
#define ss(n) scanf("%s",n);
#define for0(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define forc(i,j,n) for(ll i=j;i<n;i++)
#define pb push_back
#define sor(n) sort(n.begin(),n.end())
#define sorcmp(n) sort(n.begin(),n.end(),cmp)
#define rev(n) reverse(n.begin(),n.end())
#define pi(x)  prllf("%d",x);
#define pl(x)  prllf("%lld",x);
#define pf(x)  prllf("%.10lf",x);
#define ps(x)  prllf("%s",x);
#define en() prllf("\n");
#define random_shuffle(r...)random_shuffle(r,[](int _){return rand()%_;})
#define SQR(a) (a)*(a)
#define mod 100000007
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);}
template <typename T> T POW(T B,T P){ if(P==0) return 1; if(P&1) return B*POW(B,P-1);  else return SQR(POW(B,P/2));}
ll powmod(ll a, ll b){ll ans = 1;while(b){if(b&1) ans = ans*a%mod;a = a*a%mod;b >>= 1;}return ans;}
ll prime[1000000];bool visprime[10000000];
void sieve(){ll k=0;for(ll i=2;i*i<=1000000;i++){for(ll j=i*i;j<=1000000;j+=i){visprime[j]=true;}}for(ll i=2;i<=1000000;i++){if(visprime[i]==false) prime[k++]=i;}}


int main()
{

    int n;
    cin>>n;
    int arr[n-1];
    int ans=0;
    for(int i=0;i<n-1;i++) cin>>arr[i];
    ans+=arr[0]+arr[n-2];
    for(int i=0;i<n-2;i++)
    {
        ans+=min(arr[i],arr[i+1]);
    }
    cout<<ans<<endl;



}
























Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<math.h>
#include<string.h>
#define ll long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ff first
#define ss second
#define mem(x,y) memset(x,y,sizeof(x))
#define mod 1000000007
#define INF 0x3f3f3f3f
#define MAX 1000005
using namespace std; 

typedef pair<int, int> pii;

int solve(vector<int> &v, int k){
    int n = v.size();
    vector<int> dp(n,INT_MAX);
    dp[0] = 0;
    dp[1] = abs(v[1]-v[0]);
    for(int i=2;i<n;i++){
        for(int j=i-1;j>=max(0,i-k);j--){
            int cost = abs(v[i]-v[j]);
            dp[i] = min(cost + dp[j], dp[i]);     
        }
    }
    return dp[n-1];
}

int main(){
    int n,k;cin>>n>>k;
    vector<int> v;

    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        v.push_back(x);
    }
    cout<<solve(v,k)<<endl;        
    return 0;
}



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



bool check(vector<int>& v, int i){

	  vector<int> x = {5,7,5,7,7};
	  int id=0;
	  for(int j=i; j<v.size(); j++){

			x[id] -= v[j];
			if( x[id] == 0 ){
				  id++;
				  if(id == 5) return true;
			}
			else if( x[id] < 0 ){
				  return false;
			}
	  }
	  return false;


}


int main(){
	  while(1){
			int n; cin >> n;
			if(!n) break;

			vector<int> v(n);
			for(int i=0; i<n; i++){
				  string in; cin >> in;
				  v[i] = in.size();
			}
			for(int i=0; i<n; i++){
				  if( check(v,i) ){
						cout << i+1 << endl;
						break;
				  }
			}
			
	  }
}

Measured memory_bytes: 3144
import sys
sys.setrecursionlimit(10**6)

n,m=map(int,input().split())
d=[]
for _ in range(m):
    d.append(list(map(int,input().split())))
def ID(i):
    if i==1:
        return (d[0][0],d[0][1])
    l,r=ID(i-1)
    L=max(l,d[i-1][0])
    R=min(r,d[i-1][1])
    return (L,R)
s,g=ID(m)
print(max(g-s+1,0))

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

int main(){
    char S[3];
    char T[3];
    rep(i,3) cin >> S[i];
    rep(i,3) cin >> T[i];
    ll count=0;

    rep(i,3){
        char s = S[i];
        char t = T[i];
        if(s==t) count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int s=sc.nextInt(); //初項
        int f[]=new int[1000001];
        System.out.println(cal(s,f,0));
        
    }
    public static int cal(int s,int[]f,int count){
        f[s]++;
        count++;
        if(f[s]>=2) return count;
        if(s%2==0) s/=2;
        else s=s*3+1;
        return cal(s,f,count);
    }
}

Measured memory_bytes: 25684
package main

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

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

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	} 
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	k := scanInt()
	a := scanInt()
	b := scanInt()
	f := false
	for i := a; i < b+1; i++ {
		if i%k == 0 {
			f = true
		}
	}

	if f {
		fmt.Fprintln(wr, "OK")
	} else {
		fmt.Fprintln(wr, "NG")
	}
}


Measured memory_bytes: 1760
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll LINF = 1001002003004005006LL;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    int n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    ll ans = 1;
    rep(i,n) {
        if (a[i]==0) {
            cout << 0 << endl;
            return 0;
        }
        if (a[i] > 1000000000000000000) {
            cout << "-1" << endl;
            return 0;
        }
    }
    rep(i,n) {
        if (ans > 1000000000000000000/a[i]) {
            cout << "-1" << endl;
            return 0;
        }
        ans *= a[i];
        if (ans > 1000000000000000000) {
            cout << "-1" << endl;
            return 0;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4052
module Main (main) where
import Data.Vector ((!), (!?), Vector)
import qualified Data.Vector as V
import Control.Applicative
main :: IO ()
main = do
  n:wmax:_ <- map read . words <$> getLine
  vws <- V.replicateM n $ do
    v:w:_ <- map read . words <$> getLine
    return (v,w)
  print $ V.maximum $ solve vws (wmax + 1)

solve :: Vector (Int,Int) -> Int -> Vector Int
solve vs maxw = V.foldl' f v0 vs
  where
    v0 = V.replicate maxw 0
    f :: Vector Int -> (Int,Int) -> Vector Int
    f prev (v,w) = new
      where
        new = V.generate maxw gen
        gen i = max v1 v2
          where
            v1 = case new !? (i - w) of
              Nothing -> 0
              Just k -> k + v
            v2 = prev ! i

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

int main(){
    ll X;
    cin >> X;
    if (X % 11 == 0){
        cout << (X / 11) * 2 << endl;
    }
    else if (X % 11 <= 6){
        cout << (X / 11) * 2 + 1 << endl;
    }
    else{
        cout << (X / 11) * 2 + 2 << endl;
    }
}



Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

class MyClass
{
    public static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var x = a[n - 1];
        var i = -1;
        var t = 0;
        for (int j = 0; j < n - 1; j++)
        {
            if (a[j] <= x)
            {
                i++;
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        t = a[i + 1];
        a[i + 1] = a[n - 1];
        a[n - 1] = t;
        for (int j = 0; j < n; j++)
        {
            if (j == i + 1)
            {
                Console.Write("[" + a[j] + "]");
            }
            else
            {
                Console.Write(a[j]);
            }
            if (j != n - 1)
            {
                Console.Write(" ");
            }
        }
        Console.WriteLine();
    }
}


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

// 頂点数、変数
int v, e;
const int MAX_N = 100100;
// 隣接リスト
vector<int> g[MAX_N];
bool used[MAX_N];
// トポロジカルソートされた数列
vector<int> ans;

void dfs(int u) {
  if(used[u]) return;
  used[u] = true;
  for(auto& i: g[u]) dfs(i);
  // 帰りがけ順で追加
  ans.push_back(u);
}

int num[MAX_N];
bool used2[MAX_N];
int cou;

void dfs2(int v,int depth,int p) {
  used2[v] = true;


  rep(i,(int)g[v].size() ){
    int vnext = g[v][i];
    if (!used2[vnext] ) {
      dfs2(vnext,depth+1,v);
    }
  }
  num[v] = cou;
  cou++;
}

void tsort() {
  for(int i=0; i<v; ++i) dfs(i);
  reverse(ans.begin(), ans.end());
}

int par[MAX_N];
int diff[MAX_N];

signed main(void)
{
  ll n,m;
  cin >> n>> m;

  v = n;
  e = n + m - 1;
  for(int i=0; i<e; ++i) {
    int s, t;
    cin >> s >> t;
    s--;t--;
    g[s].push_back(t);
  }

  tsort();
  dfs2(ans[0],1,-1);

  par[ans[0]] = -1;

  rep(i,n)diff[i] = 1000000000;

  rep(i,v){
    rep(j,(int)g[i].size()) {
      if (diff[g[i][j]] > num[i] - num[g[i][j]]){
        diff[g[i][j]] = num[i] - num[g[i][j]];
        par[g[i][j]] = i;
      }
    }
  }

  rep(i,n){
    cout << par[i] + 1 << endl;
  }

  return 0;
}


Measured memory_bytes: 17396
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/icl/interval_map.hpp>

#define REPI(i, S, N) for(int i=int(S); i<int(N); i++)
#define REP(i, N) REPI(i, 0, N)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::integer;

using ll = long long;
namespace bst = boost;
namespace icl = boost::icl;
template<typename T> class in {
    T value;
public:
    in() { cin >> value; }
    operator const T&() const { return value; }
    operator T&() { return value; }
    in& operator=(T source) { value = source; return *this; }
};
template<> class in<string> : public string {
public:
    in() { cin >> *this; }
};
template<class T> class inseq : public T {
public:
    template<typename... Arg> inseq(Arg... arg) : T(forward<Arg>(arg)...) { for (auto&& i : *this) cin >> i; }
};
template<class T> using invec = inseq<vector<T>>;

auto solve() {
  in<ll> N,X,T;


  return T * ((N+X-1) / X);
}

template<typename T> void plot(const T& func) { cout << setprecision(9) << func() << endl; }
template<> void plot<void()>(void(&func)()) { func(); }

int main() {
  plot(solve);

  return 0;
}



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

int main()
{
    int l,r,d;
    cin >> l >> r >> d;
    int s=0;
    for (int n=l; n<=r; ++n) {
        if (n % d == 0) {
            ++s;
        }
    }
    cout << s;
    return 0;
}


Measured memory_bytes: 3196
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>

#define MAX_LEN 100

using namespace std;

int a[MAX_LEN];

void printArray(int *a, int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d", a[i]);
		if (i != len - 1) printf(" ");
	}
	printf("\n");
}

int main()
{
	int len;
	scanf("%d", &len);

	for (int i = 0; i < len; i++)
	{
		scanf("%d", &a[i]);
	}

	int count = 0;
	for (int i = 0; i < len - 1; i++)
	{
		bool flag = true;
		for (int j = len - 1; j > i; j--)
		{
			if (a[j - 1] > a[j])
			{
				int temp;
				temp = a[j - 1];
				a[j - 1] = a[j];
				a[j] = temp;
				count++;
				flag = false;
			}
		}
		if (flag) break;
	}
		printArray(a, len);
	printf("%d\n", count);

}


Measured memory_bytes: 3204
x,y,xx,yy=map(int,raw_input().split())
w=xx-x;h=yy-y
s='U'*h+'R'*w+'D'*h+'L'*w+'L'+'U'*(h+1)+'R'*(w+1)+'DR'+'D'*(h+1)+'L'*(w+1)+'U'
print s


Measured memory_bytes: 9072
#include <stdio.h>
#include <string.h>

int main(){
  char s[101];
  scanf("%s", s);
  int ans = 1;
  int n = strlen(s);
  for(int i = 0; i < n / 2 + n % 2; i++){
    if(s[2 * i] == 'L'){
      ans = 0;
    }
  }
  for(int i = 0; i < n / 2; i++){
    if(s[2 * i + 1] == 'R'){
      ans = 0;
    }
  }
  if(ans){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}


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

int main() {
int n,k;
cin >> n >> k;
vector<int> a(n);
rep(i,n) cin >> a.at(i);

sort(a.begin(),a.end());
reverse(a.begin(),a.end());
int ans = 0;
rep(i,k){
  ans += a.at(i);
}
cout << ans << endl;
 }


Measured memory_bytes: 3600
/**
 *    author:  FromDihPout
 *    created: 2020-08-16
**/

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;
    vector<int> cnt(n+1);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    sort(all(cnt), greater<int>());
    
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += cnt[i];
    }
    cout << n - sum << '\n';
    return 0;
}

Measured memory_bytes: 3984
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const long double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long double ABS(long double a){return max(a,-a);}
int p[110];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);
	}
	std::sort(p,p+a);
	int ret=0;
	for(int i=0;i<a;i++){
		if(p[i]<=b){
			b-=p[i];
			ret++;
		}
	}
	if(ret==a&&b)ret--;
	printf("%d\n",ret);
}

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

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            //ここから
            int[] pos = IO.ReadLineToIntArray();

            int[] ans = new int[4];

            double kakudo = Math.Atan2(pos[3] - pos[1], pos[2] - pos[0]);
            double len = Math.Sqrt(Math.Pow(pos[3] - pos[1], 2) + Math.Pow(pos[2] - pos[0], 2));
            ans[0] = (int)Math.Round(pos[0] + len * Math.Sqrt(2.0) * Math.Cos(kakudo + Math.PI/4));
            ans[1] = (int)Math.Round(pos[1] + len * Math.Sqrt(2.0) * Math.Sin(kakudo + Math.PI/4));
            ans[2] = (int)Math.Round(pos[0] + len * Math.Cos(kakudo + Math.PI/2));
            ans[3] = (int)Math.Round(pos[1] + len * Math.Sin(kakudo + Math.PI/2));

            //ここまで
            Console.WriteLine(ans[0]+" "+ans[1]+" "+ans[2]+" "+ans[3]);
            Console.ReadKey();
        }
    }
    
    class Func
    {
        long mod = 1000000007;
        static public void Swap<T>(ref T a, ref T b) { T temp = a; a = b; b = temp; }
        static public long GCD(int a, int b) { return b != 0 ? GCD(b, a % b) : a; }
        static public long LCM(int a, int b) { return (long)a * b / GCD(a, b); }
        static public int Factorial(int a) { return a == 1 ? a : a * Factorial(a - 1); }
        static public int Conbin(int n, int m) { return Factorial(n) / (Factorial(n - m) * Factorial(m)); }
        static public void Factoring(long num, ref long[] vs)
        {
            if (num == 1)
            {
                vs[1]++;
            }
            for (long i = 2; i < (long)Math.Sqrt(num); i++)
            {
                if (num % i == 0)
                {
                    vs[i]++;
                    Factoring(num / i, ref vs);
                }
            }
            vs[1]++;
        }
    }

    class IO
    {
        static public string ReadLineToString(){return Console.ReadLine();}
        static public int ReadLineToInt(){return int.Parse(Console.ReadLine());}
        static public long ReadLineToLong() { return long.Parse(Console.ReadLine()); }
        static public string[] ReadLineToStringArray(){return Console.ReadLine().Split(' ').ToArray();}
        static public int[] ReadLineToIntArray(){return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();}
        static public long[] ReadLineToLongArray() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
        static public List<string> ReadLineToStringList(){return Console.ReadLine().Split(' ').ToList();}
        static public List<int> ReadLineToIntList(){return Console.ReadLine().Split(' ').Select(int.Parse).ToList();}
        static public List<long> ReadLineToLongList() { return Console.ReadLine().Split(' ').Select(long.Parse).ToList(); }   
    }
}


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

#define mod 1000000007
 
int main(){
    int n;
	cin>>n;
	int arr[n];
	for(int i = 0;i<n;i++)cin>>arr[i];
	int gcdAll = arr[0];
	for(int i = 1;i<n;i++){
		gcdAll = __gcd(gcdAll,arr[i]);
	}
	vector<set<int> > st(n);
	for(int i = 0;i<n;i++){
		int m = arr[i];
		for(int j = 2;j*j<=m;j++){
			while(m % j == 0){
				st[i].insert(j);
				m /= j;
			}
		}
		if(m > 1)st[i].insert(m);
	}
	int total_size = 0;
	for(int i = 0;i<n;i++){
		total_size += st[i].size();
	}
	set<int> s;
	for(int i = 0;i<n;i++){
		for(auto it:st[i]){
			s.insert(it);
		}
	}
	bool pairco = ((int)s.size() == total_size);
	if(gcdAll == 1 && !pairco){
		cout<<"setwise coprime";
	}else if(pairco){
		cout<<"pairwise coprime";
	}else{
		cout<<"not coprime";
	}
    return 0;
}

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

int main() {
  ll n;
  cin >> n;
  vector<ll> x(n), y(n);
  vector<pair<ll, ll>> xy(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
    xy[i] = make_pair(x[i], y[i]);
  }

  sort(xy.begin(), xy.end(), greater<pair<ll, ll>>());
  map<pair<ll, ll>, ll> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) continue;
      ll diffX = xy[i].first - xy[j].first;
      ll diffY = xy[i].second - xy[j].second;
      m[make_pair(diffX, diffY)]++;
    }
  }
  ll mx = 0;

  for (auto v : m) {
    mx = max(mx, v.second);
  }
  cout << 1 + (n - 1) - mx << endl;
}

Measured memory_bytes: 384
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <vector>

namespace n91 {

using i8 = std::int_fast8_t;
using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
using u8 = std::uint_fast8_t;
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

constexpr usize operator"" _z(unsigned long long x) noexcept {
  return static_cast<usize>(x);
}

class rep {
  const usize f, l;

public:
  class itr {
    friend rep;
    usize i;
    constexpr itr(const usize x) noexcept : i(x) {}

  public:
    void operator++() noexcept { ++i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  constexpr rep(const usize first, const usize last) noexcept
      : f(first), l(last) {}
  constexpr itr begin() const noexcept { return itr(f); }
  constexpr itr end() const noexcept { return itr(l); }
};
class revrep {
  const usize f, l;

public:
  class itr {
    friend revrep;
    usize i;
    constexpr itr(usize x) noexcept : i(x) {}

  public:
    void operator++() noexcept { --i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}
  constexpr itr begin() const noexcept { return itr(l); }
  constexpr itr end() const noexcept { return itr(f); }
};
template <class T> using vec_alias = std::vector<T>;
template <class T> auto md_vec(const usize n, const T &value) {
  return std::vector<T>(n, value);
}
template <class... Args> auto md_vec(const usize n, Args... args) {
  return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> constexpr T difference(const T &a, const T &b) {
  return a < b ? b - a : a - b;
}

} // namespace n91

#include <algorithm>
#include <iostream>
#include <utility>

namespace n91 {

void main_() {
  u32 w, h, x, y;
  std::cin >> w >> h >> x >> y;
  std::cout << static_cast<double>(w * h) / static_cast<double>(2) << " ";
  if (x * static_cast<u32>(2) == w && y * static_cast<u32>(2) == h) {
    std::cout << "1";
  } else {
    std::cout << "0";
  }
  std::cout << std::endl;
}

} // namespace n91

int main() {
  n91::main_();
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main() {
    char s[12], t[12];
    scanf("%s", s);
    scanf("%s", t);
    int l = strlen(s);
    printf(strlen(t) - l != 1 || strncmp(s, t, l) ? "No" : "Yes");
    return 0;
}


Measured memory_bytes: 1744
#include<iostream>
#include<vector>

using namespace std;

int main()
{
    long long N, M, K, s;  cin >> N >> M >> K;
    int ans, l, j2, t, ans1, cnta, cntb, i, j, x;
    vector<long long> v(N), u(M), A(N), B(M), c(N+M);
    for(int i=0; i<N; i++){
        int a;  cin >> a;
        if(i == 0)  v[i] = a;
        else v[i] = v[i-1] + a;
        A[i] = a;
    }
    for(int i=0; i<M; i++){
        int b;  cin >> b;
        if(i == 0)  u[i] = b;
        else    u[i] = u[i-1] + b;
        B[i] = b;
    }
    j2 = 0;
    ans = 0;
    l = 0;
    t = 0;
    for(int i=N-1; i>=0; i--){
        l = 0;
        t = 0;
        s = v[i];
        for(int j=j2; j<M; j++){
            if(s + u[j] > K){
                if(s <= K)  t = i+1;
                break;
            }else{
                l = i + j + 2;
                j2 = j;
            }
        }
        l = max(t,l);
        if(l > ans) ans = l;
        if(j2 == M-1)   break;
    }
    t = 0;
    for(int i=0; i<M; i++){
        if(u[i] <= K)   t = i+1;
    }
  	ans = max(t, ans);
    i = 0;
    j = 0;
    t = 0;
    x = 0;
    cnta = 0;
    cntb = 0;
    while(x < N+M){
        if(i == N-1 && cnta == 1){
            c[x] = B[j];
            j++;
        }else if(j == M-1 && cntb == 1){
            c[x] = A[i];
            i++;
        }else if(A[i] >= B[j]){
            c[x] = B[j];
            if(j == M-1)    cntb++;
            else    j++;
        }else{
            c[x] = A[i];
            if(i == N-1)    cnta++;
            else    i++;
        }
        x++;
    }
    t = 0;
    ans1 = 0;
    i = 0;
    while(t < K){
        t += c[i];
        if(t <= K)  ans1++;
        i++;
    }
    cout << max(ans1, ans);
}

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

struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* cpp template {{{ */

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) (v).rbegin(), (v).rend()
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) REPS(i, 0, n)
#define REP1(i,n) for (ll i = 1; i <= (ll)(n); ++i)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* debug */
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; cin >> x; return x;}
inline ll IN() {ll x; cin >> x; return x;}
inline vs split(const string& t, char c) {vs v; stringstream s(t); string b; while(getline(s, b, c)) v.eb(b); return v;}
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template <typename T, typename S> inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << '\n';}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}
template <typename T> inline void print(const vector<T>& v, string s = " ") {rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}

signed main() 
{
  int x=in();
  int ans=1;
  for(int i=2;i<=sqrt(x);i++)
  {
    for(int j=1;pow(i,j)<=x;j++)
    {
      ans=max(ans,(int)pow(i,j));
    }
  }
  print(ans);

  return 0;
}

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

#define pb push_back
#define ff first
#define ss second

const long long MAXN = 1e5 + 21, inf = 1e18 + 21, LG = 20;

int n, s, w, e;
string t;

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> t;

    for (int i = 0; i < t.size(); i++) {
        if (t[i] == 'W')
            w = 1;
        else if (t[i] == 'N')
            n = 1;
        else if (t[i] == 'E')
            e = 1;
        else
            s = 1;
    }

    if ((n ^ s) == 0 && (e ^ w) == 0)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';
    return 0;
}


Measured memory_bytes: 256
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


def func(a, b, c):
    return a * a + b * b + c * c + a * b + b * c + c * a


n = inp()
limit = int(math.sqrt(n)) + 1
ans = [0] * n
for i in range(1, limit):
    for j in range(i, limit):
        for k in range(j, limit):
            x = func(i, j, k) - 1
            if x < n:
                if len(set([i, j, k])) == 1:
                    ans[x] += 1
                elif len(set([i, j, k])) == 2:
                    ans[x] += 3
                elif len(set([i, j, k])) == 3:
                    ans[x] += 6
for i in ans:
    print(i)


Measured memory_bytes: 69960