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

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> v(n);
    for (auto &x: v) cin >> x;
    sort(v.begin(), v.end());
    v[n-1] /= 2;
    cout << accumulate(v.begin(), v.end(), 0) << endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	EACH(x,vec) is >> x;
	return is;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
	return os << p.first << " " << p.second;
}
/*
template<class... T>
ostream& operator<<(ostream& os, tuple<T...>& t) {
	for (size_t i = 0; i < tuple_size< tuple<T...> >::value; ++i) {
		if (i) os << " ";
		os << get<0>(t);
	}
	return os;
}
*/
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	REP(i,vec.size()) {
		if (i) os << " ";
		os << vec[i];
	}
	return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
	REP(i,vec.size()) {
		if (i) os << endl;
		os << vec[i];
	}
	return os;
}

int H, W, M;
vector<string> m;
bool inRange(P p) {
	int x, y; tie(x, y) = p;
	return 0 <= x && x < W && 0 <= y && y < H;
}
bool isWall(P p) {
	int x, y; tie(x, y) = p;
	return m[y][x] == '#';
}
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
vector<P> bfs(P s, P t) {
	map<P, bool> used;
	map<P, P> prevV;
	queue<P> Q; Q.push(s); used[s] = true;
	while ( !Q.empty() ) {
		P p = Q.front(); Q.pop();
		REP(d, 4) {
			int nx = p.first + dx[d], ny = p.second + dy[d];
			P np(nx, ny);
			if ( inRange(np) && !isWall(np) && !used[np] ) {
				used[np] = true;
				prevV[np] = p;
				Q.push(np);
			}
		}
	}
	vector<P> res;
	for (P p = t; p != s; p = prevV[p]) {
		res.pb(p);
	}
	reverse(ALL(res));
	return res;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin >> H >> W >> M;
	m = vector<string>(H);
	cin >> m;
	vector< vector<ll> > keep(H, vector<ll>(W));
	vector< vector<ll> > on(H, vector<ll>(W));
	vector< vector<ll> > off(H, vector<ll>(W));
	cin >> keep >> on >> off;
	vector<P> tasks;
	REP(i, M) {
		int x, y; cin >> y >> x;
		tasks.pb(P(x, y));
	}
	vector<P> v; v.pb(tasks[0]);
	REP(i, M-1) {
		vector<P> path = bfs(tasks[i], tasks[i+1]);
		EACH(p, path) v.pb(p);
	}
	map<P, vector<int> > task;
	REP(i, v.size()) {
//		cout << v[i] << endl;
		task[v[i]].pb(i);
	}
	ll ans = 0;
	map<P, bool> state;
	REP(i, v.size()) {
		P& p = v[i];
		int x, y; tie(x, y) = p;
		if (!state[p]) {
			state[p] = true;
			ans += on[y][x];
		}
		auto it = upper_bound(ALL(task[p]), i);
		if (it == task[p].end()) {
			state[p] = false;
			ans += off[y][x];
		}
		else {
			int t2 = *it;
			int t = t2 - i;
			if (keep[y][x] * t <= off[y][x] + on[y][x]) {
				ans += keep[y][x] * t;
//				cout << t << endl;
			}
			else {
				state[p] = false;
				ans += off[y][x];
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 36136
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin>>s;
  if(stoi(s.substr(0,4) )>2019) cout<<"TBD";
  else if(stoi(s.substr(0,4) )==2019 && stoi(s.substr(5,2) )>4) cout<<"TBD";
  //else if(stoi(s.substr(8,2) )>30) cout<<"TBD";
  else cout<<"Heisei";
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int t, n;
  while( 1 ){
    cin >> t;
    if( !t ){ return 0; }
    cin >> n;
    int h = 0;
    for( int i = 0; i < n; i++ ){
      int s, f;
      cin >> s >> f;
      h += ( f - s );
    }
    if( t <= h ){
      cout << "OK" << endl;
      continue;
    }
    cout <<  ( t - h )  << endl;
  }
}

Measured memory_bytes: 0
# E - Sum Equals Xor
# https://atcoder.jp/contests/abc129/tasks/abc129_e

MOD = 10 ** 9 + 7

L = input()
N = len(L)

# dp[i][j]= 上から i 桁目までを決めて、その桁までが (a, b) = [(0,0),(0,1),(1,0)] の3通りから選ばれていて、
# a+b が L より小さいことが確定している(j=1)/していない(j=0)ような選び方の個数
dp = [[0] * 2 for _ in range(N + 1)]
dp[0][0] = 1

for i, s in enumerate(L):
  dp[i + 1][0] = dp[i][0] * 2 if int(s) else dp[i][0] 
  dp[i + 1][1] = dp[i][0] if int(s) else 0
  dp[i + 1][1] += dp[i][1] * 3
  dp[i + 1][0] %= MOD
  dp[i + 1][1] %= MOD

print(sum(dp[N]) % MOD)

Measured memory_bytes: 19700
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;

struct edge {LL to;LL cost;};
vector<edge> v[100001];
LL x[100001];
bool ch[100001];

void dfs(int s,int t){
    ch[s]=true;
    x[s]=t;
    for(int i=0;i<v[s].size();i++){
        edge e;
        e=v[s][i];
        if(ch[e.to]==false){
            dfs(e.to,x[s]+e.cost);
        }
    }
}

int main(){
    int N,M;
    cin >> N >> M;
    for(int i=0;i<M;i++){
        LL l,r,d;
        cin >> l >> r >> d;
        v[l].push_back({r,d});
        v[r].push_back({l,-d});
    }
    memset(x,0,sizeof(x));
    for(int i=1;i<=N;i++){
        if(ch[i]==false){
            dfs(i,0);
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<v[i].size();j++){
            if(x[v[i][j].to]-x[i]!=v[i][j].cost){
                puts("No");
                return 0;
            }
        }
    }
    puts("Yes");
    return 0;
}

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

using namespace std;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n, l, sum = 0;
    cin >> n >> l;
    for (int i = 1; i <= n; i++)
        sum += l + i - 1;
    int diff = 1 << 30, pos = 0;
    for (int i = 1; i <= n; i++)
        if (abs(l + i - 1) < diff)
            diff = abs(l + i - 1), pos = i;
    sum -= l + pos - 1;
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int N,A,B,curJ,curO;
char s[111111];
bool chk(char x){
	if(x=='c')return false;
	if(x=='a'){
		if(curJ + curO < A+B){
			curJ ++;
			return true;
		}
		return false;
	}
//if(x=='b')
	if(curJ + curO < A+B && curO < B){
		curO++;
		return true;
	}
	return false;
}
int main(){
	scanf("%d%d%d%s",&N,&A,&B,s);
	for(int i=0; i<N; i++){
		puts(chk(s[i])?"Yes":"No");
	}
	return 0;
}


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

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

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

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

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;  cin >> n;
    int count = 0;
    bool ans = true;
    vector<int> p(n), q(n), diff;
    rep(i, n) {
      cin >> p[i];
      q[i] = p[i];
    }
    sort(q.begin(), q.end());
    rep(i, n) {
      if (p[i] != q[i]) {
        count++;
        int d = abs(p[i] - q[i]);
        diff.push_back(d);
      }
    }
    if (count > 2) {
      ans = false;
    }
    if (count == 2) {
      if (diff[0] != diff[1]) {
        ans = false;
      }
    }

    if (ans) {
      cout << "YES" << '\n';
    }  else {
      cout << "NO" << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    vector< vector<int> > trump(4, vector<int>(13,0));
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        char mark;
        cin >> mark >> num;
        if(mark == 'S') {
            trump.at(0).at(num-1) = 1;
        }
        else if(mark == 'H') {
            trump.at(1).at(num-1) = 1;
        }
        else if(mark == 'C') {
            trump.at(2).at(num-1) = 1;
        }
        else if(mark == 'D') {
            trump.at(3).at(num-1) = 1;
        }
    }
    for (int j = 0; j < 4; j++) {
        for (int k = 0; k < 13; k++) {
            if (trump.at(j).at(k) == 0) {
                if (j == 0) {
                    cout << 'S' << " " << k+1 << endl;
                }
                else if (j == 1) {
                    cout << 'H' << " " << k+1 << endl;
                }
                else if (j == 2) {
                    cout << 'C' << " " << k+1 << endl;
                }
                else if (j == 3) {
                    cout << 'D' << " " << k+1 << endl;
                }
            }
        }
    }
}


Measured memory_bytes: 3020
#include <iostream>

 

using namespace std;

 

int main()
{
   int i, h, m, s;
   cin >> i;
   h = i / 3600;
   m = i / 60 - h*60; 
   s =i % 60;
   
   cout << h << ":" << m << ":" << s << endl; 
   
   return 0;
}

 


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

int main(){
  ll h,w;
  cin>>h>>w;
  ll ans=INT_MAX;
  for(int i=1; i<=w-1; i++){
    ll x,y,z;
    x=i*h;
    if(h%2==0){
      y=(h*w-x)/2; z=(h*w-x)/2; 
    }else{
      y=(w-i)*(h-1)/2; z=(w-i)*(h+1)/2;
    }
    ll ma=max(max(x,y),z), mi=min(min(x,y),z);
    ans=min(ans,ma-mi);
  }
  for(int i=1; i<=w-1; i++){
    ll x,y,z;
    x=i*h;
    if((w-i)%2==0){
      y=(h*w-x)/2; z=(h*w-x)/2; 
    }else{
      y=(w-i-1)/2*h; z=(w-i+1)/2*h;
    }
    ll ma=max(max(x,y),z), mi=min(min(x,y),z);
    ans=min(ans,ma-mi);
  }
  for(int i=1; i<=h-1; i++){
    ll x,y,z;
    x=i*w;
    if(w%2==0){
      y=(h*w-x)/2; z=(h*w-x)/2; 
    }else{
      y=(w-1)*h/2; z=(w+1)*h/2;
    }
    ll ma=max(max(x,y),z), mi=min(min(x,y),z);
    ans=min(ans,ma-mi);
  }
  for(int i=1; i<=h-1; i++){
    ll x,y,z;
    x=i*w;
    if((h-i)%2==0){
      y=(h*w-x)/2; z=(h*w-x)/2; 
    }else{
      y=(h-i-1)*w/2; z=(h-i+1)*w/2;
    }
    ll ma=max(max(x,y),z), mi=min(min(x,y),z);
    ans=min(ans,ma-mi);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N,M,C;
    cin>>N>>M>>C;
    int B[M],A[N][M];
    
    for(int i=0;i<M;i++)cin>>B[i];
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)cin>>A[i][j];
    }
    
    int ans=0;
    for(int i=0;i<N;i++){
        int sum=C;
        for(int j=0;j<M;j++){
            sum+=A[i][j]*B[j];
        }
        if(sum>0)ans++;
    }
    
    cout<<ans<<endl;
}

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

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

using namespace std;

const int64_t INF = INT64_C(1000000000000);

struct Data {
  int64_t num;
  Data() : num(-INF) {;}
  Data(int64_t n) : num(n) {;}
};

inline Data Merge(Data left, Data right) {
  return Data(left.num > right.num ? left.num : right.num);
}

struct SegmentTree {
  static const int STsize = 1 << 18;
  Data data[STsize]; int n;
  SegmentTree(void) : n(STsize / 2) {}
  void update (int pos, Data value) {
    if (data[pos].num >= value.num) return;
    data[pos] = value;
    while (pos < 2*n-1) {
      int l = pos, r = pos^1;
      pos = pos / 2 + n;
      data[pos] = Merge(data[l], data[r]);
    }
  }
  Data sub(int fr, int to, int node, int la, int ra) {
    if (ra<=fr || to<=la) return Data();
    if (fr<=la && ra<=to) return data[node];
    Data vl = sub(fr, to, (node-n)*2+0, la, (la+ra)/2);
    Data vr = sub(fr, to, (node-n)*2+1, (la+ra)/2, ra);
    return Merge(vl, vr);
  }
  Data query(int fr, int to) { return sub(fr, to, 2*n-2, 0, n); }
};

int main() {
  int n;
  cin>>n;
  SegmentTree st;
  int64_t sum = 0;
  st.update(0, 0);
  REP(i,n){
    int x;
    cin>>x;
    sum += x;
    int64_t v = st.query(0, x).num;
    st.update(x, v+x);
  }
  cout << (sum - st.query(0, n+1).num) << endl;
  return 0;
}

Measured memory_bytes: 3212
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>
#include<functional>
#include<deque>

using namespace std;
typedef long long int ll;

#define C cout<<
#define E <<endl

ll n,m,aa[100010],ab[100010],ch=0;
vector<ll> va,vb;


void sortvecll(vector<ll> &target, vector<ll> &secondnum)
{
    int vecsize=target.size();
    vector<ll> baseint,target2(vecsize),secondnum2(vecsize);
    for(int i=0;i<vecsize;i++)baseint.push_back(i);
    sort(baseint.begin(),baseint.end(),[&](ll a,ll b){return target[a]<target[b];});
    for(int i=0;i<vecsize;i++){
        target2[i]=target[baseint[i]];
        secondnum2[i]=secondnum[baseint[i]];
    }
    target=target2;secondnum=secondnum2;
}

int main(){
    
    cin>>n>>m;
    
    for(int i=0;i<n;i++){
        cin>>aa[i]>>ab[i];
        va.push_back(aa[i]);
        vb.push_back(ab[i]);
    }
    
    sortvecll(va,vb);
    
    for(int i=0;i<n;i++){
        if(vb[i]<m){
            ch+=va[i]*vb[i];
            m-=vb[i];
        }
        else{
            ch+=va[i]*m;
            break;
        }
        //C va[i]<<" "<<vb[i] E;
        
    }
    C ch E;
}

Measured memory_bytes: 6508
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll a,b;
    cin >> a >> b;
    cout << min(a%b,b-(a%b)) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<iomanip>
#define BUG puts("no bug")
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define REP(a,b,c) for(ll a=b;a<=c;a++)
#define PER(a,b,c) for(ll a=b;a>=c;a--)
#define lb(a) (a&(-a))
#define pp (p<<1)
#define ppp (p<<1|1)
#define pi pair<ll,ll>
#define pii pair<pair<ll,ll>,ll>
using namespace std;
const ll MAXN=1e6+5;
ll n,m,t;
ll v[MAXN];
char s[MAXN];
int main(){
    ll a=100;
    cin>>n;
    REP(i,1,1000000000){
        a=a/100+a;
        if(a>=n){
            cout<<i;
            break;
        }
    }
}

Measured memory_bytes: 3188
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

typedef basic_string<int> IS;

int main(){
  for(int a,b,c,d,e,na,nb,nc;cin>>a>>b>>c>>d>>e>>na>>nb>>nc,a;){
    IS is=IS(nc,c)+IS(nb,b)+IS(na,a);
    int m,cs=a*na+b*nb+c*nc;
    m=cs;
    for(int i=0;i<is.size();i++){
      cs-=is[i];
      m=min(m,cs+max(i+1,d)*e);
    }
    cout<<m<<endl;
  }
}

  
  

Measured memory_bytes: 4380
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifdef LOCAL
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;
#else
#define debug(x) ;
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

/* SimpleSegTree(0-index) */

struct SimpleSegTree{
  typedef ll Type;
  int segn2;
  Type initVal;
  vector<Type> data;
  function<Type(Type, Type)> merge;

  SimpleSegTree(int n, Type initVal, function<Type(Type, Type)> merge):
    initVal(initVal), merge(merge)
  {
    for(segn2=1; segn2<n; segn2*=2);
    data.assign(segn2*2, initVal);
  }

  SimpleSegTree(int n): //RangeMinimunQuery
    SimpleSegTree(n, -INF, [](Type a, Type b){ return max(a, b); }) {}

  SimpleSegTree(int n, Type initVal): //RangeMinimunQuery
    SimpleSegTree(n, initVal, [](Type a, Type b){ return max(a, b); }) {}

  //get value [a,b)
  Type query(int a, int b, int l = 0, int r = -1, int k = 0){
    if(r == -1) r = segn2;
    if(a <= l && r <= b) return data[k];
    if(r <= a || b <= l) return initVal;
    return merge(query(a,b,l,(l+r)/2,k*2+1),query(a,b,(l+r)/2,r,k*2+2));
  }

  //set kth number x
  void set(int k, Type x){
    k += segn2-1;
    data[k] = x;
    while(k > 0){
      k = (k-1)/2;
      data[k] = merge(data[k*2+1], data[k*2+2]);
    }
  }
};



int main(){
  int n, h[SIZE], a[SIZE];

  scanf("%d", &n);

  for(int i=0;i<n;i++) scanf("%d", h+i);
  for(int i=0;i<n;i++) scanf("%d", a+i);

  SimpleSegTree seg(n+1);
  seg.set(0, 0);

  for(int i=0;i<n;i++){
    ll p = seg.query(0, h[i]);
    seg.set(h[i], p+a[i]);
  }

  cout << seg.query(0, n+1) << endl;

  return 0;
}


Measured memory_bytes: 5888
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

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

	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a.at(i);
	}
	sort(all(a));

	cout << a.back() - a.front() << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, ans =0;
    cin >> n;
    int a[n],b[n],c[n-1];
    for(int i =0 ; i <n ;++i){
        cin >> a[i];
    }
    for(int j =0 ; j <n ;++j){
        cin >> b[j];
    }
    for(int l =0 ; l <n-1 ;++l){
        cin >> c[l];
    }
    for(int k = 0; k <n; ++k){
        int z = a[k];
        ans += b[z-1];
        if(k!=0){
            int y = a[k-1], x=a[k] ;
            if(x == y + 1){
                ans += c[y-1] ;
            }
        }
    }
    cout<<ans;


}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ull  unsigned long long
#define pb push_back
#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 1100000;
int s[N], a[N];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (a[i] > 0){
            s[i % 2] += a[i];
        }
    }
    vector < int > b;
    int k;
    if (s[0] > s[1]) k = 0; else k = 1;
    for (int i = 1; i <= n; i++) if (i % 2 == k && a[i] > 0) b.pb(i);
    vector < int > ans;
    if (b.size() == 0){
        int x = -2e9, p;
        for (int i = 1; i <= n; i++){
            if (a[i] > x){
                x = a[i];
                p = i;
            }
        }
        cout << x << endl;
        cout << n - 1 << endl;
        for (int i = n; i > p; i--) cout << i << " ";
        for (int i = 1; i < p; i++) cout << 1 << " ";
        return 0;
    }
    int sz = n;
    for (int i = 1; i < b[0]; i++){
        ans.pb(1);
        sz--;
    }
    int x = n - sz;
    for (int i = n; i > b.back(); i--){
        ans.pb(sz);
        sz--;
    }
    for (int i = 0; i < b.size() - 1; i++){
        int l = b[i];
        int r = b[i + 1];
        int l0 = l;
        int y = l + 2;
        while(l + 2 < r){
            ans.pb(y - x);
            l += 2;
        }
        ans.pb(y - 1 - x);
        x += r - l0;
    }
    cout << s[k] << endl;
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
}


Measured memory_bytes: 2304
#include<bits/stdc++.h>
using namespace std;
long long mod = 1e9 + 7;
int main(){
    int n;
    cin >> n;
    vector<long long>v(n + 3), suff(n + 3);
    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }
    suff[n + 1] = 0;
    for(int i = n; i >= 0; i--){
        suff[i] = (suff[i + 1] + v[i]) % mod;
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        ans = (ans + v[i] * suff[i + 1]) % mod;
    }
    cout << ans;
    return 0;
}

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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define INF LONG_LONG_MAX
#define MOD 1000000007
#define yn(f) cout << (f ? "Yes" : "No") << endl;
#define YN(f) cout << (f ? "YES" : "NO") << endl;

int a,b,n,ans;


signed main() {
    cin >> a >> b >> n;
    int x = min(b-1, n);
    cout << (a*x)/b - a*(x/b) << endl;
}




Measured memory_bytes: 3636
#!/bin/python3
 
import sys
 
G1 = [1, 3, 5, 7, 8, 10, 12]
G2 = [4, 6, 9, 11]
 
x,y = input().strip().split(' ')
x,y = [int(x),int(y)]
 
if x in G1 and y in G1:
    print("Yes")
elif x in G2 and y in G2:
    print("Yes")
else:
    print("No")

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

using namespace std;

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

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> P;

const ll INF = 1ll<<30;
const ll MOD = 1000000007;
const double EPS  = 1e-10;

int main() {
	string s;
	cin >> s;
	
	int ans = INF;
	REP(i, s.size()) {
		int cnt = 0;
		
		string t = s;
		while (true) {
			if (t.size() == 0 || count(ALL(t), s[i]) == t.size()) break;
			string tmp = "";
			REP(j, t.size() - 1) {
				if (t[j] == s[i]) tmp += t[j];
				else tmp += t[j + 1];
			}
			t = tmp;
			cnt++;
		}
		
		chmin(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;

int main()
{

    ll ans = 0;
    int n, t;
    cin >> n >> t;
    int a[n];
    rep(i, n) cin >> a[i];

    rep(i, n - 1) ans += (a[i + 1] - a[i] < t ? a[i + 1] - a[i] : t);

    OP(ans + t);

    return 0;
}

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

int main()
{
    int N, K;
    cin>>N>>K;
    vector<long long> P(N);
    for (long long &p: P)
        cin>>p, p--;
    vector<long long> C(N);
    for (long long &c: C)
        cin>>c;

    long long ans = -1000000000;
    for (int o=0; o<N; o++)
    {
        int ln = 1;
        long long lc = C[o];
        for (int p=P[o]; p!=o; p=P[p])
        {
            ln++;
            lc += C[p];
        }

        if (K/ln>=1)
            ans = max(ans, K/ln*lc);

        int n = 0;
        long long c = 0;
        for (int p=P[o]; p!=o; p=P[p])
        {
            n++;
            c += C[p];
            if (n>K)
                break;
            ans = max(ans, c);
            ans = max(ans, c+(K-n)/ln*lc);
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3272
import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s,t=LS()
  a,b=LI()

  u=S()

  if u==s:
    print(a-1,b)
  else:
    print(a,b-1)

main()
# print(main())


Measured memory_bytes: 5972
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

int main(){
    long long n, m;
    cin >> n >> m;

    vector<long long>Pref(m), Year(m);
    vector<vector<long long> > pref_year(n+1);

    for(long long i = 0; i < m; i++){
        cin >> Pref[i] >> Year[i];
        pref_year[Pref[i]].push_back(Year[i]);
    }

    map<long long, long long> year_rank;
    for(long long i = 0; i <= n; i++){
        sort(pref_year[i].begin(), pref_year[i].end());
        for(long long j = 0; j < pref_year[i].size(); j++){
            year_rank[pref_year[i][j]] = j+1;
        }
    }

    for(long long i = 0; i < m; i++){
        //printf("year_rank[Year[i]] %lld\n", year_rank[Year[i]]);
        printf("%06lld%06lld\n", Pref[i], year_rank[Year[i]]);
    }

    return 0;
}

Measured memory_bytes: 14848
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FPEN freopen("in.txt", "r", stdin);
#define debug(...) \
  { cerr << "# " << __VA_ARGS__ << "\n"; }
#else
#define debug(...)
#define FPEN
#endif
const int maxn = 300009;
typedef long long i64;
typedef pair<i64, i64> pi64;
typedef pair<int, int> pi;
const i64 MOD = 1e9 + 7;
class {
 public:
  void solve() {
    int n;
    cin >> n;
    vector<i64> a(n);
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    i64 ans = 0, two = 1;
    for (int i = 0; i <= 60; ++i) {
      i64 zero = 0, one = 0, count = 0;
      for (int j = 0; j < n; ++j)
        if (a[j] >> i & 1ll)
          one++;
        else
          zero++;
      for (int j = 0; j < n - 1; ++j) {
        if (a[j] >> i & 1ll) {
          one--;
          count += zero;
        } else {
          zero--;
          count += one;
        }
        count %= MOD;
      }
      (ans += two * count % MOD) %= MOD;
      two = two * 2 % MOD;
    }
    cout << (ans % MOD + MOD) % MOD << '\n';
  }
} NSPACE;
int main() {
  FPEN;
  ios_base::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  NSPACE.solve();
}

Measured memory_bytes: 2560
import java.util.Arrays;
import java.util.Scanner;

//Goldbach's Conjecture
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		boolean[] p = new boolean[50001];
		Arrays.fill(p, true);
		p[0] = p[1] = false;
		for(int i=2;i<50001;i++)if(p[i])for(int j=i*2;j<50001;j+=i)p[j]=false;
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			int c = 0;
			for(int i=2;i<=n/2;i++)if(p[i]&&p[n-i])c++;
			System.out.println(c);
		}
	}
}

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

int a[200001];

int main(){
    int n,k; cin >> n >> k;
    for(int i=0;i<n;i++){
        int b; cin >> b;
        a[b-1]++;
    }
    sort(a,a+n);
    int ans=0;
    for(int i=n-k-1;i>=0;i--){
        ans+=a[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
bool prime(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};


  
int main(){
  int l,r;
  cin>>l>>r;
  
  if(r-l>=2019){
    cout<<0<<endl;
    return 0;
  }
  
  l %= 2019;
  r %= 2019;
  
  vector<int> temp;
  while(true){
    temp.push_back(l);
    l = (l+1)%2019;
    if(l==r){
      temp.push_back(r);
      break;
    }else{
      continue;
    }
  }
  
  int n=temp.size();
  int ans=2019;
  REP(i,n){
    REP(j,i){
      ans = min(ans,(temp[i]*temp[j])%2019);
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
 int main(){
   int a,b,c;
   cin >>a>>b;
   c=a/b;
   if(a%b!=0){
     c++;
   }
   cout<<c<<endl;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m, q = map(int, input().split())
abcd = [0] * q
for i in range(q):
    abcd[i] = list(map(int, input().split()))

def dfs(seq):
    if len(seq) == n:
        yield seq
    else:
        if seq:
            last = seq[-1]
        else:
            last = 1
        for i in range(last, m+1):
            new_seq = seq.copy()
            new_seq.append(i)
            yield from dfs(new_seq)

seq = dfs([])
ans = 0
for s in seq:
    tmp_ans = 0
    for a, b, c, d in abcd:
        if s[b-1] - s[a-1] == c:
            tmp_ans += d
    ans = max(ans, tmp_ans)
print(ans)


Measured memory_bytes: 83952
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a,b,c,x,y,i;
    long long int s[3],min;
    scanf("%d%d%d%d%d",&a,&b,&c,&x,&y);
    if(x>=y)
    {s[0]=x*2*c;
    s[1]=y*2*c+(x-y)*a;
    s[2]=x*a+y*b;
    }
    else
    {s[0]=y*2*c;
    s[1]=x*2*c+(y-x)*b;
    s[2]=x*a+y*b;
    }
    min=s[0];
    for(i=1;i<3;i++)
    {
        if(s[i]<min)
            min=s[i];
    }
    printf("%I64d",min);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#include <vector>
#include <numeric>
#include <map>
#include <cmath>
#include <iomanip>
#include <set>
using ll =long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;
using vvs = vector<vs>;

ll mod = 1000000000 + 7;
int main(){
    int A, B, C;
    cin >> A >> B >> C;

    for(ll i =1; i<=B; i++){
        if(A*i%B == C){
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int a[55],b[55],c[55],d[55];
int flag[55];
int ff[55];
#define ll long long
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>c[i]>>d[i];
    }
    int anspos=0;
    for(int i=1;i<=n;i++)
    {
        ll mins=1000000007;
        for(int j=1;j<=m;j++)
        {
            ll s=abs(a[i]-c[j])+abs(b[i]-d[j]);
            if(mins>s)
            {
                mins=s;
                anspos=j;
            }
        }
        cout<<anspos<<endl;
    }
   /* int anspos=0;
    for(int i=1; i<=m; i++)
    {
        cin>>c[i]>>d[i];
        ll mins=1000000007;
        for(int j=1; j<=n; j++)
        {
            if(flag[j])
                continue;
            ll s=abs(c[i]-a[j])+abs(d[i]-b[j]);
            if(mins>s)
            {
                mins=s;
                anspos=j;
            }


        }
        if(flag[anspos])
            continue;
        else
        {
            cout<<anspos<<endl;
            flag[anspos]=1;
        }


    }
    */
    return 0;
}


Measured memory_bytes: 256
def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

import math
N= n_in()
print(math.ceil(N/2))


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=a; i<=b; i++)
#define per(i,a,b) for (register int i=a; i>=b; i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 20200000, mo = 1e9+7;
int n,m,k,fac[N],ifac[N],tot,totn,totm;
int power(int a, int n){
	int res=1;
	while(n){
		if(n&1)res=1LL*res*a%mo;a=1LL*a*a%mo;n>>=1;
	}
	return res;
}
void init(int n){
	fac[0]=1;rep(i,1,n)fac[i]=1LL*fac[i-1]*i%mo;
	ifac[n]=power(fac[n],mo-2);per(i,n-1,0)ifac[i]=1LL*ifac[i+1]*(i+1)%mo;
}
int C(int n, int m){return m>=0&&m<=n?1LL*fac[n]*ifac[m]%mo*ifac[n-m]%mo:0;}
int calc(int n, int m,int k){
	int res=0;rep(i,0,n)res=(res+1LL*C(n,i)*C(m,k-i))%mo;
	return 1LL*res*fac[k]%mo;
}
int main() {
	read(n);read(m);read(k);init(N-1);
	tot=calc(n-1,m-1,k-2);
	totn=calc(n-1,m,k-1);
	totm=calc(n,m-1,k-1);
	//printf("%d %d %d\n",tot,totn,totm);
	ll res=1LL*k*calc(n,m,k)%mo;
	rep(i,1,k){
		ll now=(1LL*n*totn+1LL*m*totm+1LL*n*m%mo*(i-1)%mo*tot%mo*2LL)%mo;
		res=(res+now%mo*(k-i+1))%mo;
	}
	cout<<res;
	return 0;
}

Measured memory_bytes: 158080
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;

int main(){
    string str;
    cin>>str;
    int z = str.size();
    if(str[0]==str[z-1]){
        if(z%2==0){
            cout<<"First"<<endl;
        }else{
            cout<<"Second"<<endl;
            
        }
    }else{
        if(z%2==0){
            cout<<"Second"<<endl;
        }else{
            cout<<"First"<<endl;
            
        }
    }
    
    
    
    
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX;
#define INFL LLONG_MAX;
typedef long long ll;
using namespace std;

int main(){
  int n; cin >> n;
  vector<int> a(n,0);

  vector<int> col(8+1);

  rep(i,n){
    cin >> a.at(i);
    int c = min(a[i]/400,8);
    col[c]++;
  }

  int Max=0;
  int Min=0;
  int rest=0;
  rep(i,8){
    if(col[i]>0) Max++;
    else rest++;
  }

  Min = Max;

  if(rest==8) Min++;
  Max += col[8];

  cout << Min << " " << Max <<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

bool seg[][7]={
	{0,1,1,1,1,1,1},
	{0,0,0,0,1,1,0},
	{1,0,1,1,0,1,1},
	{1,0,0,1,1,1,1},
	{1,1,0,0,1,1,0},
	
	{1,1,0,1,1,0,1},
	{1,1,1,1,1,0,1},
	{0,1,0,0,1,1,1},
	{1,1,1,1,1,1,1},
	{1,1,0,1,1,1,1}
};

int main()
{
	int n,t; bool st[7];
	while(cin>>n,~n){
		rep(i,7)st[i]=0;
		rep(i,n){
			cin>>t;
			char ans[8]={0};
			rep(i,7){
				ans[i]=st[i]^seg[t][i]?'1':'0';
				st[i]=seg[t][i];
			}
			cout<<ans<<endl;
		}
	}
	
	return 0;
}

Measured memory_bytes: 0
import math

A, B, H, M = list(map(int, input().split()))

A_deg = 30.0 * H + 0.5 * M
B_deg = 6.0 * M

print(math.sqrt(A ** 2 + B ** 2 - 2.0 * A * B *  math.cos(math.radians(A_deg-B_deg))))

Measured memory_bytes: 9436
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <random>
#include <fstream>
#define rep(i, n) for (int i = 0; i < n; i++)
#define PI 3.14159265358979323846
#define MOD 1000000007
using namespace std;
using ll = long long;

const int MAX = 1000000;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  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 COM(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 gcd(ll a, ll b)
{
  ll r;
  while ((r = a % b))
  {
    a = b;
    b = r;
  }
  return b;
}

template <class T> struct cord{
  T x,y;
};

template <class T> double dist(cord<T> a, cord<T> b){
  T dx=a.x-b.x;
  T dy=a.y-b.y;
  return sqrt(dx*dx+dy*dy);
}

int main()
{

  //cout << fixed << setprecision(10);

  int a,b; cin >> a >> b;
  if (a%3==0 || b%3==0 || (a+b)%3==0){cout << "Possible";}
  else {cout << "Impossible";}

  return 0;
}


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

const int Maxn = 15;

int n, d;
int X[Maxn][Maxn];
int res;

bool Check(int a, int b)
{
    int res = 0;
    for (int i = 0; i < d; i++)
        res += (X[a][i] - X[b][i]) * (X[a][i] - X[b][i]);
    int sq = sqrt(double(res));
    while (sq * sq < res) sq++;
    while (sq * sq > res) sq--;
    return sq * sq == res;
}

int main()
{
    scanf("%d %d", &n, &d);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++)
            scanf("%d", &X[i][j]);
        for (int j = 0; j < i; j++)
            res += Check(j, i);
    }
    printf("%d\n", res);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int64_t> H(n);
    for(int i = 0;i < n;i++) {
        cin >> H.at(i);
    }
    if(n == 1) {
        cout << "Yes" << endl;
        return 0;
    }
    for(int i = n - 1;i > 0;i--) {
        if(H.at(i - 1) - 1 == H.at(i)) {
            H.at(i - 1)--;
        }else if(H.at(i - 1) > H.at(i)) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

enum result{ NOT_FOUND = -1 };
const int ALPHABET_SIZE = 26;
std::vector<std::string> keyWords = { "the", "that", "this" };

char caesar(const char&, const int);
std::string decode(std::string, int);
bool isKeyWord(std::string);
int askKey(std::vector<std::string>);
std::string dataShaping(std::string);

int  main(){

	std::string str;
	while (std::getline(std::cin, str)){
		std::vector<std::string> cryptography;
		int key;
		std::stringstream ss{ str };
		std::string word;

		while (std::getline(ss, word, ' '))
		{
			cryptography.push_back(word);
		}

		key = askKey(cryptography);
		if (key == NOT_FOUND){
			std::cout << "NOT_FOUND\n";
			return -1;
		}

		for (size_t i = 0; i < cryptography.size(); i++)
		{

			std::cout << decode(cryptography[i], key);
			if (i != cryptography.size() - 1){
				std::cout << ' ';
			}
		}

		std::cout << std::endl;
	}
	return 0;
}


char caesar(const char& chara, const int KEY){
	if (chara >= 'a' && chara <= 'z'){
		int charaIndex = chara - 'a';
		charaIndex = (charaIndex + KEY) % ALPHABET_SIZE;
		return 'a' + charaIndex;
	}
	return chara;
}

std::string decode(std::string str, int key){
	std::string decodedTexts;
	for (auto& chara : str)
	{
		decodedTexts += caesar(chara, key);
	}
	return decodedTexts;
}

bool isKeyWord(std::string str){
	for (auto& keyWord : keyWords)
	{
		if (dataShaping(str) == keyWord){
			return true;
		}
	}
	return false;
}

int askKey(std::vector<std::string> cryptography){
	for (auto& str : cryptography)
	{
		for (size_t i = 0; i <= ALPHABET_SIZE; i++)
		{
			if (isKeyWord(decode(str, i)))
			{
				return i;
			}
		}
	}
	return NOT_FOUND;
}

std::string dataShaping(std::string word){
	unsigned int wordSize = word.size();
	if (word[wordSize - 1] < 'a' || word[wordSize - 1] > 'z'){
		return word.substr(0, wordSize - 1);
	}
	return word;
}



Measured memory_bytes: 3044
N, K, S = map(int, input().split())
if S != 10 ** 9:
    a = 10 ** 9
else:
    a = 1

a = [str(S)] * K + [str(a)] * (N-K)
ans = ""
for i in range(N):
    ans += a[i] + " "
print(ans)

Measured memory_bytes: 7908
#include <iostream>
#include <math.h>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

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

typedef long long lint;

using namespace std;

int main(){
  int N,K;
  cin>>N>>K;
  lint ans=K;
  REP(i,N-1)ans*=(K-1);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(void){
    // Your code here!
    long long int a,b,x,A,B;
    cin>>a>>b>>x;
    if (a==0){cout<<1+b/x<<endl;}
    else{cout<<b/x-(a-1)/x<<endl;}
    return 0;
} 


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;

char c[101][102];
int f[101][102];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",c[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(i==1&&j==1){
				f[i][j]=(c[i][j]=='#');
				continue;
			}
			f[i][j]=2e9;
			if(i!=1)f[i][j]=min(f[i][j],f[i-1][j]+(c[i-1][j]=='.'&&c[i][j]=='#'));
			if(j!=1)f[i][j]=min(f[i][j],f[i][j-1]+(c[i][j-1]=='.'&&c[i][j]=='#'));
		}
	printf("%d\n",f[n][m]);
}


Measured memory_bytes: 1768
def wa(t):
    sum=0
    while t>0:
       sum+=t%10
       t//=10
    return sum

n=int(input())
ans=[]
for i in range(1,n):
    ans.append(wa(i)+wa(n-i)) 
    if wa(i)+wa(n-i)==1:
        print(i)
print(min(ans))

Measured memory_bytes: 3864
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<string>
#include<sstream>
using namespace std;
typedef set<string>S;
const int SIZE=1<<17;
int Bit[SIZE],P;
int Sum(int i)
{
	int s=0;
	for(;i;i^=(i&-i))
		s=(s+Bit[i])%P;
	return s;
}
void Add(int i, int v)
{
	for(;i<SIZE;i+=(i&-i))
		Bit[i]=(Bit[i]+v)%P;
}
int main()
{
	int A,B,i,r,x,v;
	stringstream ss;
	while(scanf("%d%d%d",&A,&B,&P),A)
	{
		S s;
		memset(Bit,r=0,sizeof(Bit));
		for(i=A;i<=B;++i)
		{
			ss.str("");
			ss<<i;
			s.insert(ss.str());
		}
		for(S::iterator ite=s.begin();ite!=s.end();++ite)
		{
			x=atoi(ite->c_str());
			i=x-A+1;
			v=Sum(i)+1;
			Add(i,v);
			r=(r+v)%P;
		}
		printf("%d\n",r);
	}
	return 0;
}

Measured memory_bytes: 7020
#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    if ((a - b) % 2 != 0) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        int c = int((a + b) / 2);
        cout << c << endl;
    }
}

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

using namespace std;
typedef long long ll;
const ll mx = 10000007;
using pii = pair<ll, ll>;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
#define ull unsigned long long
#define    ss   second
#define    ff   first
#define    pb   push_back
#define gcd(a, b) __gcd((a), (b))
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))

///--------------Graph Moves--------------------------------------
///const ll fx[] = {+1,-1,+0,+0};
///const ll fy[] = {+0,+0,+1,-1};
///const ll fx[] = {+0,+0,+1,-1,-1,+1,-1,+1}; ///King's move
///const ll fy[] = {-1,+1,+0,+0,+1,+1,-1,-1}; ///king's Move
///const ll fx[] = {-2,-2,-1,-1,+1,+1,+2,+2}; ///knight's move
///const ll fy[] = {-1,+1,-2,+2,-2,+2,-1,+1}; ///knight's move
///---------------------------------------------------------------

#define FIO ios_base::sync_with_stdio(false);  cin.tie(NULL);


int main() {
    FIO;

    ll n; cin >> n;
    ll s = 0;
    ll a[n + 2];
    for(ll i = 0; i < n; i++) {
        cin >> a[i];
        s += a[i];
    }
    ll b = ceil(s / (1.0 * n));
    ll c = floor(s / (1.0 * n));
    ll ans = INT_MAX;

    ll s1 = 0, s2 = 0;
    for(ll i = 0; i < n; i++) {
        s1 += (((a[i]) - (b)) * ((a[i]) - (b)));
    }

    for(ll i = 0; i < n; i++) {
        s2 += (((a[i]) - (c)) * ((a[i]) - (c)));
    }

    cout << min(s1, s2) << endl;

    return 0;
}


Measured memory_bytes: 3752
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long MAXN=200005,MOD=1e9+7;
long long n;
long long a[MAXN];
long long c[MAXN];
long long d[MAXN];
int main()
{
	scanf("%lld",&n);
	for(long long i=1;i<=n;i++)
	{
		long long C;
		scanf("%lld",&C);
		a[c[C]]=i;
		c[C]=i;
	}
	a[0]=0;
	d[1]=1;
	for(long long i=1;i<n;i++)
	{
		if(a[i]!=0&&a[i]!=i+1)
		{
			d[a[i]]+=d[i];
			d[a[i]]%=MOD;
		}
		d[i+1]=(d[i+1]+d[i])%MOD;
	}
	printf("%lld\n",d[n]);
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if (abs(a - c) <= d) cout << "Yes" << endl;
  else if (abs(a - b) <= d && abs(b - c) <= d) cout << "Yes" << endl;
  else cout << "No" << endl;


  
  return 0;
}

Measured memory_bytes: 256
import sys
N=int(input())
dt=0
dx=0
dy=0
for i in range(N):
  t,x,y=map(int,input().split())
  t=t-dt
  x=x-dx
  y=y-dy
  if(x+y > t):
    print('No')
    sys.exit()
  if( (x+y)%2==0 and t%2==1 ):
    print('No')
    sys.exit()
  elif( (x+y)%2==1 and t%2==0 ):
    print('No')
    sys.exit()
print('Yes')

Measured memory_bytes: 3064