akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;

bool isSquare(int n) {
    int r = floor(sqrt((long double) n));
    return (r * r) == n;
}

int main() {
    int n, d;
    cin >> n >> d;
    vector<vector<int>> x(n, vector<int>(d));
    rep(i, n) {
        rep(j, d) cin >> x.at(i).at(j);
    }

    int count = 0;
    rep(i, n-1) {
        for(int j = i+1; j < n; j++) {
            int dis = 0;
            rep(k, d) {
                dis += (x.at(i).at(k) - x.at(j).at(k)) * (x.at(i).at(k) - x.at(j).at(k));
            }
            if(isSquare(dis)) count++;
        }
    }
    cout << count << endl;

    return 0;
}

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


////////// 	Template structure for debugging

#define tr(...) trace(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void trace(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void trace(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cout.write(names, comma-names) << " : " << arg1 << " | " ; 

trace(comma+1, args...);
}

#define print(...) pr(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void pr(const char* name, Arg1&& arg1){
cout << arg1 << endl;
}
template <typename Arg1, typename... Args>
void pr(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cout << arg1 << " "; 
pr(comma+1, args...);
}

void printV(vector<int> &arr)
{
for(int i=0;i<arr.size();i++)cout << arr[i] << " \n"[ i == arr.size()-1 ];
}

///////////////// Fenwick Tree 
// void update(int index,int num){

// 	while(index<=N){
// 		arr[index] += num;
// 		index += index & (-index);
// 		//cout << index << endl;
// 	}

// }

// int sum(int index){

// 	int s = 0;
// 	while(index){
// 		s += arr[index];
// 		index -= index & (-index);
// 	}
// 	return s;
// }

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

/////////////////// Type definitions
typedef long long ll;
typedef pair<int,int> pi;
#define f first
#define s second
////////////////////////////////////////////////////////////////////////////

int t;
void solve(){}	

struct Node{
	int a,b,c;
};


int main(){

	int n;
	cin >> n;
	vector<Node> arr;
	for(int i=0;i<n;i++){
		arr.push_back(Node());
		cin >> arr[i].a >> arr[i].b >> arr[i].c;
	}

	int dp[n][3];

	for(int i=0;i<n;i++){

		if(i==0)dp[i][0] = arr[i].a,dp[i][1] = arr[i].b,dp[i][2] = arr[i].c;
		else {
			dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + arr[i].a;
			dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + arr[i].b;
			dp[i][2] = max(dp[i-1][1],dp[i-1][0]) + arr[i].c;
		}

	}
	cout << max(max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
}

Measured memory_bytes: 5624
#include<bits/stdc++.h>
using namespace std;
 
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,a,b)    for(int i=a;i<b;i++)
#define repn(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define mp  make_pair
#define all(v) (v).begin(), (v).end()
#define hell 1000000007  
#define hell2 998244353 
#define pi 3.14159265358979323846

int solve(){   
    string s,t;
    cin>>s>>t;
    int a=0;
    rep(i,0,s.size()) if(s[i]!=t[i]) a++;
    cout<<a;
    return 0;   
}
 
signed main(){
    IOS;
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 3724
from collections import deque
K = int(input())
count = 0
todo = deque(range(1, 10))
while todo:
    x = todo.popleft()
    count += 1
    if count == K:
        print(x)
        break
    i = x % 10
    if 0 < i:
        todo.append(x * 10 + i - 1)
    todo.append(x * 10 + i)
    if i < 9:
        todo.append(x * 10 + i + 1)

Measured memory_bytes: 18972
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
bool odd(const int &n) { return n & 1; }
bool even(const int &n) { return ~n & 1; }
template<typename T = int> T in() { T x; cin >> x; return x; }
template<typename T = int> T in(T &&x) { T z(forward<T>(x)); cin >> z; return z; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename A, typename B> istream &operator>>(istream &is, pair<A, B> &p) { return is >> p.first >> p.second; }
template<typename T> ostream &operator<<(ostream &os, const vector<vector<T>> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : "\n"); return os; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "" : " "); return os; }
template<typename A, typename B> ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << p.first << ' ' << p.second; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
// clang-format on

main {
  while (true) {
    int n = in();
    if (n == 0) break;
    vector<int> x(n), y(n), r(n), c(n);
    rep(i, n) cin >> x[i] >> y[i] >> r[i] >> c[i];
    auto intersectCC = [&](int i, int j) {
      int r2 = (r[i] + r[j]) * (r[i] + r[j]);
      int d = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
      return d < r2;
    };
    auto intersect = [&](int t, int used) {
      bool f = false;
      rep(i, t) f |= (~used >> i & 1) && intersectCC(t, i);
      return f;
    };
    vector<int8_t> dp(1 << n, -1);
    function<int(int)> dfs = [&](int used) {
      if (dp[used] != -1) return dp[used];
      cmax(dp[used], 0);
      rep(i, n) loop(j, i + 1, n) {
        if ((used >> i & 1) || (used >> j & 1) || c[i] != c[j]) continue;
        if (intersect(i, used) || intersect(j, used)) continue;
        cmax(dp[used], dfs(used | (1 << i) | (1 << j)) + 2);
      }
      return dp[used];
    };
    cout << dfs(0) << endl;
  }
}



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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

	int N, K; cin >> N >> K;

	int now = 1;
	for (int i = 0;i < N;i++){
		if(now*2 - now < K) now *= 2;
		else now += K;
	}

	cout << now << endl;

	return 0;

}


Measured memory_bytes: 384
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<cstring>
#include<bitset>
#include<stack>
#include<time.h>



#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define ALL(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define getmid ((l+r)>>1)
#define mst(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define lowbit(x) x&(-x)
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
#ifdef local
#define dbg(args...) cout << #args << " -> ", err(args);
void err(){ cout << endl; }
template<typename T, typename... Args>
void err(T a, Args... args){ cout << a << ' '; err(args...); }
#else
#define dbg(args...)
#endif // local

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <double, double> pdd;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const long double eps=1e-8;
const int mod=1e9+7;
const int maxn=3e5+100;
const int N=1e6+1000;
const int M=500+10;
const ll mm=(1LL<<32);

template <class T>
inline void read(T &x)
{
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar())
        f ^= c == '-';
    for (; isdigit(c); c = getchar())
        x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10)
        ++len;
    for (; len; --len, x %= y, y /= 10)
        putchar(x / y + 48);
}
ll qpow(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}

int fa[N],sz[N];
int fd(int x)
{
    return x==fa[x]?x:fa[x]=fd(fa[x]);
}
int main()
{
#ifdef local
    freopen("in.txt","r",stdin);
#endif // local
    IOS;cout.tie(0);
    int n,m;cin>>n>>m;
    rep1(i,n) fa[i]=i,sz[i]=1;
    int ans=1;
    rep1(i,m){
        int u,v;cin>>u>>v;
        u=fd(u),v=fd(v);
        if(u!=v)
        {
            fa[u]=v;
            sz[v]+=sz[u];
            ans=max(ans,sz[v]);
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 5224
#include <bits/stdc++.h>
using namespace std;
bool isprime(int x){
 bool flg = true;
 int y = 2;
 while(y*y<x){
  if (x%y==0){
   flg = false;
   break;
  }
  y++;
 }
 return flg;
}
int main(void){
 int X;
 cin >> X;
 while(1){
  if (isprime(X)){
   cout << X;
   break;
  }
  X++;
 }
}


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

const int maxn = 810;
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int h, w, K, dist[maxn][maxn];
char s[maxn][maxn];
bool vis[maxn][maxn];
queue<pair<int, int>> q;

int main() {
    scanf("%d %d %d", &h, &w, &K);
    int sx, sy;
    for (int i = 1; i <= h; i++) {
        scanf("%s", s[i] + 1);
        for (int j = 1; j <= w; j++) {
            if (s[i][j] == 'S') sx = i, sy = j;
        }
    }
    vis[sx][sy] = 1, q.push({sx, sy});
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        int x = p.first, y = p.second;
        if (dist[x][y] == K) break;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || nx > h || ny < 1 || ny > w) continue;
            if (vis[nx][ny] || s[nx][ny] == '#') continue;
            dist[nx][ny] = dist[x][y] + 1;
            vis[nx][ny] = 1, q.push({nx, ny});
        }
    }
    int ans = 1e9;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) if (vis[i][j]) {
            int num = min({i - 1, h - i, j - 1, w - j});
            ans = min(ans, (num + K - 1) / K + 1);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 4096
import java.util.HashMap;
import java.util.Scanner;

/*
問題文

*/

public class Main {
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] s = new String[n];

        HashMap<String, Integer> list = new HashMap<>();
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();
            if (list.containsKey(s[i])) {
                list.put(s[i], list.get(s[i]) + 1);
            } else {
                list.put(s[i], 0);
            }
        }
        System.out.println(list.size());
    }
}

Measured memory_bytes: 77676
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 200000;
int main()
{
  int a[MAX];
  int b[MAX];
  int n;
  cin >> n;
  for (int i=0;i<n;i++)
  {
    cin >> a[i];
    b[i]=a[i];
  }
  sort(a,a+n);
  for (int i=0;i<n;i++)
  {
    if (b[i]==a[n-1]) cout << a[n-2] <<endl;
    else
      cout << a[n-1] <<endl;
  }
  return 0;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
// int a[100010],n,j;
int main()
{
  int size;
  cin >>size;
  long long  a[size];
  for(int i=0;i<size;i++)
    cin >> a[i];
  long long ans=0;
  long long suffix[size];
  long long sum=a[size-1];
  suffix[size-1]=a[size-1];
  for(int i=size-2;i>=1;i--)
  {
     sum+=a[i];
     sum%=mod;
     suffix[i]=sum;
  }
  for(int i=0;i<size-1;i++)
  {
    ans+=(a[i]%mod)*(suffix[i+1]%mod)%mod;
    ans%=mod;
  }
  cout << ans << endl;
  // for(int i=1;i<size;i++)
  //   cout << suffix[i] << " " ;
   
}

Measured memory_bytes: 6752
#include<stdio.h>
#include<algorithm>

using namespace std;
int main()
{
	long long a,b,c,d;
	while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d))
	{
		long long n;
		n=max(a*c,a*d);
		n=max(n,c*b);
		n=max(n,b*d);
		printf("%lld\n",n);
	}
	return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	const long long mod = 1e9 + 7;
	cin >> n;
	vector< vector<int> >a(n, vector<int>(n));
	vector<long long>dp(1 << n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> a[i][j];
	dp[0] = 1;
	for (int i = 0; i < 1 << n; i++) {
		int num = 0;
		for (int j = 0; j < n; j++)
			if (i >> j & 1)
				num++;
		for (int j = 0; j < n; j++)
			if (i >> j & 1 && a[num - 1][j])
				dp[i] = (dp[i] + dp[i ^ 1 << j]) % mod;
	}
	cout << dp[(1 << n) - 1] << '\n';
	return 0;
}

Measured memory_bytes: 19484
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const ll INF = 1001001001;
const ll LINF = 1001001001001001001;

void prvec(vector<ll> vec){
    ll n = vec.size();
    rep(i,n) cout << i << " " << vec.at(i) << "\n";
}

void pr2d(vector<vector<ll>> vvec){
    ll h = vvec.size();
    ll w = vvec.at(0).size();
    rep(i,h){
        rep(j,w){
            cout << vvec.at(i).at(j) << " ";
        }
        cout << "\n";
    }
}

long long modpow(long long a,long long n, long long mod){
    long long res = 1;
    while(n>0){
        if ( n & 1 ) res = (res * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}

ll binary_divide_mod(string s, ll x){
    if(x<=0) return INF;
    ll ss = s.size();
    ll z = 0;
    rep(i,ss){
        z = 2*z + (s.at(i)-'0');
        if(z<x) continue;
        z -= x;
    }
    return z;
}

int main(){
    //下準備
    vector<ll> lst(200002);
    for(int i=0;i<=200001;i++){
        ll x = i;
        ll count = 0;
        while(x!=0){
            bitset<20> b(x);
            ll y = b.count();
            x = x%y;
            count++;
        }
        //bitset<20> bb(i);
        //cout << i << " " << bb << " " << count << endl;
        lst.at(i) = count;
    }

    ll n ; cin >> n;
    string x; cin >> x;
    ll xs = x.size();
    ll cnt_1 = 0;
    rep(i,xs) if(x.at(i)=='1') cnt_1++;

    ll plus = cnt_1 + 1, minus = cnt_1 - 1;

    //2進割り算;
    ll mplus = binary_divide_mod(x,plus);
    ll mminus = binary_divide_mod(x,minus);

    rep(i,n){
        bool pORm = (x.at(i)-'0');
        ll ans;
        if(pORm){ //上からi桁目が1 つまり1から0に反転する;
            //X-2^(N-i) % A-1を求めたい
            if(mminus==INF){
                cout << 0 << endl;
                continue;
            }
            ll amari = (mminus - modpow(2,n-i-1,minus)) % minus;
            if(amari<0) amari += minus;
            ans = 1 + lst.at(amari);
        }else{ //上からi桁目が0 つまり0から1に反転する;
            //X+2^(N-i) % A+1 を求めたい
            ll amari = (mplus + modpow(2,n-i-1,plus)) % plus;
            ans = 1 + lst.at(amari);
        }
        cout << ans << endl;
    }
    return 0;    
}

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

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

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

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    int white_cnt = 0;
    REP(i, h) {
        cin >> s[i];
        REP(j, w)if(s[i][j] == '.') white_cnt++;
    }
    vector<VI> dist(h, VI(w, INT_MAX));

    // BFS, 幅優先探索
    queue<pair<int, int>> search_q;
    search_q.push(make_pair(0, 0));
    dist[0][0] = 0;
    while(search_q.size() > 0) {
        int x = search_q.front().first;
        int y = search_q.front().second;
        search_q.pop();
        REP(i, 4) {
            int adj_x = x + dx[i];
            int adj_y = y + dy[i];
            if(adj_x < 0 or h <= adj_x) continue;
            if(adj_y < 0 or w <= adj_y) continue;
            if(s[adj_x][adj_y] == '.' and dist[adj_x][adj_y] == INT_MAX) {
                search_q.push(make_pair(adj_x, adj_y));
                dist[adj_x][adj_y] = dist[x][y] + 1;
                if(adj_x == h - 1 and adj_y == w - 1) {
                    cout << white_cnt - dist[h - 1][w - 1] - 1 << endl;
                    return 0;
                }
            }       
        }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 256
x,y = map(int,input().split())
ans = float("inf")
if y>=x:
  ans = min(ans,y-x)
if -y>=x:
  ans = min(ans,-y-x+1)
if -y>=-x:
  ans = min(ans,-y+x+2)
if y>=-x:
  ans = min(ans,y+x+1)
print(ans)

Measured memory_bytes: 38384
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <map>
#include <limits>
using namespace std;
typedef long long ll;

float inf = std::numeric_limits<float>::infinity();
ll mod = 1e9+7;

/* 二次元配列の宣言
  vector<vector<int>> tb;
  tb.resize(H);
  for (size_t i = 0; i < H; i++) {
    tb[i].resize(W);
  }
*/
/*
  A.resize(N);
  for (int i = 0; i < N; i++) {scanf("%d",&A[i]);}
*/

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

  vector<int> tb;
  tb.resize(N);
  ll a;
  for (size_t i = 0; i < N; i++) {
    cin >> a;
    if (a>=N){
      cout << 0;
      exit(0);
    }
    tb[a] += 1;
  }

  ll ind,ans=1;
  for (size_t i = 0; i < (N+1)/2; i++) {
    ind = (2-N%2) + i*2;
    if(ind-1 ==0){
      if(tb[0]!=1){
        cout << 0 << endl;
        exit(0);
      }
    }else{
      if(tb[ind-1] != 2){
        cout << 0 << endl;
        exit(0);
      }
    ans *= 2;
    ans %= mod;
    }
  }
  cout << ans;
}


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

int main() {
    /* Input */
    int N;
    cin >> N;
   
    /* Main Logic */
    int ones_place = N % 10;

    /* Output */
    if (ones_place == 0) cout << "pon" << endl;
    if (ones_place == 1) cout << "pon" << endl;
    if (ones_place == 2) cout << "hon" << endl;
    if (ones_place == 3) cout << "bon" << endl;
    if (ones_place == 4) cout << "hon" << endl;
    if (ones_place == 5) cout << "hon" << endl;
    if (ones_place == 6) cout << "pon" << endl;
    if (ones_place == 7) cout << "hon" << endl;
    if (ones_place == 8) cout << "pon" << endl;
    if (ones_place == 9) cout << "hon" << endl;
    
    return 0;
}

Measured memory_bytes: 3648
/**
 * Title: D - Knapsack 1
 * Url: https://atcoder.jp/contests/dp/tasks/dp_d
 */
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int MAX_N = 100;
const int MAX_W = 100000;
int N, W;
int w[MAX_N+1], v[MAX_N+1];
ll dp[MAX_N+1][MAX_W+1];

ll rec(int i, int weight) {
    if(dp[i][weight] != -1) return dp[i][weight];
    if(i==N) return dp[i][weight] = 0;
    if(weight - w[i] < 0) return rec(i+1, weight);
    return dp[i][weight] = max(rec(i+1, weight), rec(i+1, weight-w[i])+v[i]);
}

int main() {

    memset(dp, -1, sizeof(dp));

    cin >> N >> W;
    for(int i=0; i<N; i++) cin >> w[i] >> v[i];

    cout << rec(0, W) << endl;

    return 0;
}

Measured memory_bytes: 79104
N, M = map(int, input().split())
E = {i: [] for i in range(N)}
for _ in range(M):
    u, v = map(int, input().split())
    E[u-1].append(v-1)
    E[v-1].append(u-1)

q = [(0, [0])]
c = 0
while q:
    x, p = q.pop()

    if len(p) == N:
        c += 1

    for v in E[x]:
        if v in p:
            continue
        q.append((v, p + [v]))

print(c)


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

using namespace std;

int ans;

int x, y;

int main() {
	scanf("%d%d", &x, &y);
	if (x == 1 && y == 1) {
		cout << 1000000 << endl;
		return 0;
	} 
	else {
		if (x == 1) ans += 300000;
		else if (x == 2) ans += 200000;
		else if (x == 3) ans += 100000;
		if (y == 1) ans += 300000;
		else if (y == 2) ans += 200000;
		else if (y == 3) ans += 100000;
	}
	cout  << ans << endl;
	return 0;
}

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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define Edge pair< i_i, int>
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Endl endl
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    Int(n);
    string st;
    cin >> st;

    int sum = 0, add = 0;

    rep(i, n) {
        if (st[i] == ')') {
            if (add) {
                add--;
            } else {
                sum++;
            }
        } else {
            add++;
        }
    }

    rep(i, sum) {
        cout << "(";
    }
    cout << st;

    /*   
    for (int i = st.size() -1; i >= 0; i--) {
        if (st[i] == ')') {
            if (add) {
                add--;
            } else {
                sum++;
            }
        } else {
            add++;
        }
    }
    */
    
    rep(i, add) {
        cout << ")";
    }
    cout << endl;




    return 0;
}



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

using namespace std;

string s, ans;

int main() {
    cin >> s;
    
    ans.assign(s.begin(), s.end() - 8);

    cout << ans << endl;

    return 0;
}

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

const int MOD = 1000000007;
int main() {
	int N;
	cin >> N;
	int64_t power = 1;
	for (int i = 2;i <= N;i ++) power = power * i % MOD;
	cout << power;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

総積のmodはmodの総積に等しいので、毎回modすればいい
ちなみに、10^9+7は素数なので、これを利用した定理(逆元をフェルマーの小定理から求める等)には注意ね
*/

Measured memory_bytes: 256
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
//package dp;

/**
 *
 * @author aakas
 */
import java.util.*;
public class Main {
    static int n;
    static boolean[] v1;
    static int[] dp4;
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        v1 = new boolean[n];
        dp4 = new int[n];
        int[] height = new int[n+2];
        for(int i=0;i<n;i++)
        {
            height[i] = sc.nextInt();
        }
        height[n] = height[n+1] = 100000;
        System.out.println(dp3(0,height));
    }
    public static int dp3(int i,int[] height)
    {
        if(i==n-1)
            return 0;
        if(i>=n)
            return 100000;
        if(v1[i])
            return dp4[i];
        v1[i] = true;
        return dp4[i] = Math.min(dp3(i+1,height)+Math.abs(height[i+1]-height[i]),dp3(i+2,height)+Math.abs(height[i+2]-height[i]));
       
    }
}


Measured memory_bytes: 72924
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mt make_tuple
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector <long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector < pair <long long int,long long int> >
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int inf = 1e9 + 5;
const ll inf64 = 1e18 + 5;

bool ck(string &s)
{
	for(int i = 0; i < s.length(); i++) {
		if(s[i] != s[(int)s.length() - i - 1])
		return false;
	}
	return true;
}
int main()
{
	boost;
	int n, i;
	string s;
	cin >> s;
	n = s.length();
	string a, b;
	fo(i, 0, n / 2)
	a.pb(s[i]);
	fo(i, (n + 2) / 2, n)
	b.pb(s[i]);
	if(ck(s) && ck(a) && ck(b))
	cout << "Yes";
	else
	cout << "No";
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author vikas.k
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int x = in.nextInt();
            int y = in.nextInt();

            out.print((x * y) % 2 == 0 ? "Even" : "Odd");
        }

    }

    static class FastScanner {
        private BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;

        public FastScanner(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String next() {
            if (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 21460
#include <bits/stdc++.h>
using namespace std;
 
long long n,m;
vector<long long> a,b,ans;
int main(){
  long long i,j,p,sum=0,T=1,count =0,ansum=0;
  cin >> n;
  for(i=0;i<n;i++){
    cin >> p;
    a.push_back(p);
  }
  for(i=0;i<n;i++){
    cin >> p;
    b.push_back(p);
  }
 
  //solve
  for(i=0;i<30;i++){
    vector<long long>now = b;
    for(j=0;j<n;j++){
      now[j] %= T*2;
    }
    sort(now.begin(),now.end());
    for(j=0;j<n;j++){
      long long x = a[j];
      x %= T*2;
      count += (lower_bound(now.begin(),now.end(),2*T-x) - lower_bound(now.begin(),now.end(),T-x));
          count += (lower_bound(now.begin(),now.end(),4*T-x) - lower_bound(now.begin(),now.end(),3*T-x));
    }
    if(count%2==1)ans.push_back(1);
    else ans.push_back(0);
    count =0;
    T *=2;
  }
 
  p=1;
  for(i=0;i<30;i++){
    ansum += ans[i]*p;
    p*=2;
  }
  cout << ansum << endl;
  return 0;
}

Measured memory_bytes: 5104
s = input()

pos = len(s)
while pos > 0:
    # print(s[pos-6:pos])
    if s[pos-1] == 'e':
        if s[pos-5:pos] == 'erase':
            # print(s[pos-5:pos])
            pos -= 5
        else:
            break
    elif s[pos-1] == 'm':
        if s[pos-5:pos] == 'dream':
            # print(s[pos-5:pos])
            pos -= 5
        else:
            break
    elif s[pos-6:pos] == 'eraser':
        # print(s[pos-6:pos])
        pos -= 6
    elif s[pos-7:pos] == 'dreamer':
        # print(s[pos-7:pos])
        pos -= 7
    else:
        break
print('YES' if pos <= 0 else 'NO')



Measured memory_bytes: 3188
#include <cstdio>
#include <cstdint>

int main() {
  intmax_t S;
  scanf("%jd", &S);

  intmax_t lb = -1;
  intmax_t ub = 1e9;
  while (ub-lb > 1) {
    intmax_t mid = (lb+ub) >> 1;
    ((mid*mid < S)? lb: ub) = mid;
  }
  intmax_t a = ub;
  intmax_t b = 1;
  intmax_t c = ub*ub - S;
  intmax_t d = ub;
  printf("0 0 %jd %jd %jd %jd\n", a, b, c, d);
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int64_t N,T;
int main(){
  cin>>N>>T;
  vector<int64_t>A(N);
  for(int i=0;i<N;i++)
    cin>>A.at(i);
  int64_t m=A.at(0);int64_t M=0;int count=0;
  for(int i=1;i<N;i++){
  if(m<A.at(i)){
  if(M<A.at(i)-m){M=A.at(i)-m;count=1;}else if(M==A.at(i)-m)count++;else{}
  }else{
  m=A.at(i);
  }
     }cout<<count<<endl;
  return 0;
}

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

int main(){
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '1'){
            s[i] = '9';
        } else {
            s[i] = '1';
        }
    }
    cout << s << endl;
    return 0;
}


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

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

    if(k % 2 == 1)
        cout << ll(pow(n / k, 3)) << endl;
    else{
        int count = 0;
        rep(i, n){
            if(i % k == k / 2)
                count++;
        }
        cout << ll(pow(n / k, 3)) + ll(pow(count, 3)) << endl;
    }
}


Measured memory_bytes: 256
//
//  main.cpp
//  CoderTest
//
//  Created by yuya on 2019/05/20.
//  Copyright © 2019 yuya. All rights reserved.
//

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


int main(){
    
    string S,T;
    cin >> S >> T;
    
    vector<char> trans(26), invs(26);
    int impsbl = 0;
    
    
    for(int i=0;i<S.length();i++){
        if(trans[S[i]-'a'] < 'a') {
            trans[S[i]-'a'] = T[i];
            if(invs[T[i]-'a'] < 'a'){
                invs[T[i]-'a'] = S[i];
            } else {
                impsbl = 1;
                break;
            }
        } else if(trans[S[i]-'a'] != T[i]) {
            impsbl = 1;
            break;
        }
    }
    
    if(impsbl) cout << "No" << endl;
    else cout << "Yes" << endl;
    
    
    
    return 0;
}




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

int64_t aa[100010];
int main()
{
  ll a,x = 0,q = 0;
  string b, y;
  
  cin >> a >> b;
  
  x += (b[0] - '0') * 100;
  x += (b[2] - '0') * 10;
  x += (b[3] - '0') * 1;
  ll c = a*x;
  
  cout << c / 100 << endl;
  
    
  return 0;
}


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

const ll MAX = 1e9;
ll s;

int main() {
    cin >> s;
    if(s == 1e18) {
        printf("0 0 %d 0 0 %d\n", MAX, MAX);
        return 0;
    }

    ll a, b, c, d;
    a = MAX;
    b = 1;
    d = s/MAX + 1;
    c = MAX - s%MAX;
    printf("0 0 %d %d %d %d\n",a,b,c,d);
}

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

int main(void) {
  int a, b, c;
  cin >> a >> b >> c;
  if (a < c && c < b) cout << "Yes" << endl;
  else if (b < c && c < a) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 768
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
typedef long long ll;

using namespace std;


int main(){
    string S;
    int N;
    cin >> N;
    cin >> S;
    int cnt=0;
    for(int i=0;i<=N-3;i++){
        if(S[i] == 'A' && S[i+1] == 'B' && S[i+2] == 'C'){
            cnt++;
        }
    }
    cout << cnt;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<math.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<=n;++i)
double len(pair<ll,ll> a,pair<ll,ll> b){
  double l=sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
  return l;
}
int main(){
  int n;
  cin>>n;
  vector<pair<ll,ll>> r(n);
  rep(i,n){
    cin>>r[i].first>>r[i].second;
  }
  double ans=0;
  rep(i,n){
    for(int j=i+1;j<n;j++){
      ans+=len(r[i],r[j]);
    }
  }
  ans=ans*2/n;
  printf("%.12lf\n",ans);
  return 0;
}


Measured memory_bytes: 256
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv) {
  int  a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  printf((a == b && a != c) || (a == c && a != b) || (b == c && b != a) ? "Yes\n" : "No\n");
  return EXIT_SUCCESS;
}


Measured memory_bytes: 128
def m():
    h, w = map(int, input().split())
    if h % 3 == 0 or w % 3 == 0:
        return 0
    ans = 9999999999

    for i in range(h):
        if ((h * w) - i * w) % 2 == 0:
            tmp = ((h * w) - i * w) // 2
            ans = min(ans, abs(tmp - (i * w)))
            continue
        c = ((h*w) - i*w) // (h - i)
        tmp = (c // 2) * (h - i)
        another = (c // 2 + 1) * (h - i)
        big = max(tmp, another, i*w)
        small = min(tmp, another, i*w)
        ans = min(ans, abs(big - small))

    for j in range(w):
        if ((h * w) - j*h) % 2 == 0:
            tmp = ((h * w) - j * h) // 2
            ans = min(ans, abs(tmp - (j * h)))
            continue
        c = ((h*w) - j*h) // (w - j)
        tmp = (c // 2) * (w - j)
        another = (c // 2 + 1) * (w - j)
        big = max(tmp, another, j*h)
        small = min(tmp, another, j*h)
        ans = min(ans, abs(big - small))

    return ans
print(m())

Measured memory_bytes: 3064
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
d = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [-1, -1], [1, -1], [-1, 1]]

for i in range(h):
    for j in range(w):
        cnt = 0
        if s[i][j] == ".":
            for k in d:
                if 0 <= i + k[0] <= h-1 and 0 <= j + k[1] <= w-1:
                    if s[i+k[0]][j+k[1]] == "#":
                        cnt += 1
        if s[i][j] == "#":
            continue
        s[i][j] = str(cnt)

for i in s:
    print("".join(i))

Measured memory_bytes: 39792
def solve():
    n = int(input())
    dp = [0] * (n + 1)
    
    def update(i, x):
        while i <= n:
            if dp[i] < x:
                dp[i] = x
            i += i & -i
    
    def get_sum(i):
        s = 0
        while i > 0:
            t = dp[i]
            if s < t:
                s = t
            i -= i & -i
        return s
    
    A = map(int, input().split())
    
    for a_i in A:
        update(a_i, get_sum(a_i - 1) + a_i)
    
    ans = n * (n + 1) // 2 - get_sum(n)
    print(ans)

solve()


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

int main() {
	// your code goes here
	int n,i,b[200],sum=0;
	cin >> n;
	for(i=1;i<n;i++){
		cin >> b[i];
	}
	for(i=1;i<=n;i++){
		if(i==1) sum+=b[1];
		else if(i==n) sum+=b[n-1];
		else sum+=min(b[i-1],b[i]);
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
x, k, d = map(int, input().split())

if x >= 0:
    if x >= k * d:
        print(x - k * d)
    else:
        q, mod = divmod(x, d)
        k -= q
        if k % 2 == 0:
            print(mod)
        else:
            print(abs(mod - d))
else:
    if abs(x) >= k * d:
        print(abs(x) - k * d)
    else:
        q, mod = divmod(abs(x), d)
        k -= q
        if k % 2 == 0:
            print(mod)
        else:
            print(abs(mod - d))


Measured memory_bytes: 9040
def main(N, A):
    # mode = 'up' or 'down'
    lst = A[:2]
    if A[0] <= A[1]:
        first_mode = 'up'
    else:
        first_mode = 'down'
    mode = first_mode

    for a in A[2:]:
        if mode == 'up':
            if lst[-1] <= a:
                lst[-1] = a
            else:
                lst.append(a)
                mode = 'down'
        else:   # mode == 'down'
            if lst[-1] >= a:
                lst[-1] = a
            else:
                lst.append(a)
                mode = 'up'

    money = 1000
    if first_mode == 'down' and len(lst) == 2:
        print(money)
        exit()
    elif first_mode == 'down':
        del lst[0]
    # else:   # first_mode == 'up'

    for n in range(len(lst) // 2):
        shou = money // lst[2*n]
        amari = money % lst[2*n]
        money = shou * lst[2*n+1] + amari
        
    print(money)




if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    main(N, A)


Measured memory_bytes: 9248
# 定数
INF = float("inf")
MOD = int(1e9 + 7)

# エントリーポイント
def main():
    N = int(input())
    g = [[] for _ in range(N)]
    for n in range(N - 1):
        u, v, w = map(int, input().split())
        u, v, w = u - 1, v - 1, w % 2
        g[u].append((v, w))
        g[v].append((u, w))
    rs, visited, que = [0] * N, [False] * N, [0]
    while que:
        c = que.pop(0)
        if visited[c]: continue
        visited[c] = True
        for n, w in g[c]:
            if visited[n]: continue
            rs[n] = (rs[c] + w) % 2
            que.append(n)
    for r in rs:
        print(r)

main()


Measured memory_bytes: 36332
#!/usr/bin/env python
# coding: utf-8

# In[13]:


import math


# In[11]:


N,H = map(int, input().split())
a_list = [];b_list = []
for _ in range(N):
    a,b = map(int,input().split())
    a_list.append(a)
    b_list.append(b)


# In[14]:


a_max = max(a_list)
b_list = sorted(b_list,reverse=True)
b_list.append(0)
h = H
ans = 0
for b in b_list:
    if b >= a_max:
        ans += 1
        h -= b
        if h <= 0:
            break
    else:
        ans += math.ceil(h/a_max)
        break
print(ans)


# In[ ]:






Measured memory_bytes: 17876
#include<stdio.h>
int main(void) {
	int A, B, K, i;
	scanf("%d %d %d", &A, &B, &K);
	if (A + (K - 1) >= B - (K - 1)){
		for (i = A; i <= B; i++) {
			printf("%d\n", i);
		}
	}
	else {
		for (i = A; i <= A + (K - 1); i++) {
			printf("%d\n", i);
		}
		for (i = B - (K - 1); i <= B; i++) {
			printf("%d\n", i);
		}
	}
	return 0;
}


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

int main(){
    int n,k;
    cin>>n>>k;
    vector<long long> v(n);
    for(int i=0;i<n;++i) cin>>v[i];


    long long ans=0;
    int m=min(n,k);
    for(int i=0;i<=m;++i){
        for(int j=0;i+j<=m;++j){
            vector<long long> t;
            long long cur=0;
            for(int l=0;l<i;++l){
                t.push_back(v[l]);
                cur+=v[l];
            }
            for(int l=0;l<j;++l){
                t.push_back(v[n-1-l]);
                cur+=v[n-1-l];
            }
            sort(t.begin(),t.end());
            int o=min<int>(t.size(),k-i-j);
            for(int l=0;l<o;++l){
                if(t[l]<0) cur-=t[l];
            }
            ans=max(ans,cur);
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 3624
import numpy as np
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
ans=1e15
for i in range(1<<N):
    B = [0]*M
    C = 0
    for j in range(N):
        if i%2:
            B = [x + y for (x, y) in zip(A[j][1:], B)]
            C += A[j][0]
        i = i//2
    if all(B[i]>=X for i in range(M)):
        ans=min(ans,C)
if ans>=1e15:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 27076
# -*- coding: utf-8 -*-

L = int(input())
A = [int(input()) for _ in range(L)]

DP = [0] * 5
#  ----- L ----- S ----- G ----- R -----
# |--0--| |--1--| |--2--| |--3--| |--4--|
# |--*--| |--偶--| |--奇--| |--偶--| |--*--|
for i in range(L):
    DP[4] = min(DP[0:5]) + A[i]
    DP[3] = min(DP[0:4]) + (A[i] % 2 if A[i] != 0 else 2)
    DP[2] = min(DP[0:3]) + ((A[i] + 1) % 2)
    DP[1] = min(DP[0:2]) + (A[i] % 2 if A[i] != 0 else 2)
    DP[0] = DP[0] + A[i]

print(min(DP))


Measured memory_bytes: 11040
#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;

int main(){
	string s1=" ";
	int sum=0;

	while(1){
		cin >> s1;
		if(s1=="0") break;
		sum = 0;
		for(int i=0;i<s1.length();i++){
			sum += (int)s1[i] - '0';
		}
		cout << sum << endl;
	}
	return 0;
}

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

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

#define ll long long int
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define MOD 1000000007

bool isvowel(char c)
{
    if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')
        return true;
    else
        return false;
}
ll isprime(ll n)
{
    for(ll i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
            return i;
    }
    return 1;
}
ll power(ll a,ll b)
{
    if(b==0)
        return 1;
    if(b==1)
        return a%MOD;
    ll temp=power(a,b/2);
    if(b%2==0)
        return ((temp%MOD)*(temp%MOD))%MOD;
    else
        return ((((temp%MOD)*(temp%MOD))%MOD)*a%MOD)%MOD;
}

/*-----------------------------------------------------------------------------*/
//ll dp[100001][100001]={0};
ll fun(ll a,ll b)
{
    ostringstream str1;
    str1<<a;
    string s1=str1.str();
    ostringstream str2;
    str2<<b;
    string s2=str2.str();
    string s="";
    for(ll i=0;i<s1.length();i++)
    {
        s+=s1[i];
        s+=s2[i];
    }
    stringstream g(s);
    ll x=0;
    g>>x;
    return x;
}
int main()
{
    //ios_base::sync_with_stdio(false);
	//cin.tie(NULL);


    //freopen("leapfrog_ch_.txt","rt",stdin);
    //freopen("output.txt","wt",stdout);

    ll t;
    t=1;
    //cin>>t;
    while(t--)
    {
      ll n;
      cin>>n;
      ll p[n+1];
      for(ll i=1;i<n+1;i++)
        cin>>p[i];
     ll count1=0;
      for(ll i=1;i<=n;i++)
      {
          if(p[i]!=i)
          {
              if(count1!=0)
              {
                  cout<<"NO";
                  return 0;
              }
              else
              {
                  if(p[p[i]]==i)
                  {
                      swap(p[i],p[p[i]]);
                      count1++;
                  }
                  else
                  {
                      cout<<"NO";
                      return 0;
                  }
              }
          }
      }
      cout<<"YES";
    }
    return 0;
}


Measured memory_bytes: 256
mod = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = sum(a) % mod
a2 = [a[i]**2 % mod for i in range(n)]
s2 = sum(a2) % mod
ans2 = (s**2 - s2) % mod
if ans2 % 2 == 0:
  print(ans2 // 2)
else:
  print((ans2 + mod) // 2)


Measured memory_bytes: 31616
n=int(input())
a=list(map(int,input().split()))
a.append(0)
r=[abs(a[0])]
for i in range(1,n+1):
    r.append(abs(a[i]-a[i-1]))

l=0
ans=sum(r)
for i in range(n):
    if l<=a[i]<=a[i+1] or l>=a[i]>=a[i+1]:
        print(ans)
    else:
        print(ans-2*min(r[i],r[i+1]))
    l=a[i]


Measured memory_bytes: 13920
using System;

namespace AtCoder {
	class Program {
		public static void Main() {
			long n = long.Parse(Console.ReadLine());
			for (int a = 1; a <= 3500; a++) {
				for (int b = 1; b <= 3500; b++) {
					// 4/n = 1/a + 1/b + 1/c
					// 4abc = nbc + nac + nab
					// 4abc - nbc - nac = nab
					// c (4ab - na - nb) = nab
					// c = nab / (4ab - na - nb)
					long x = n * a * b;
					long y = 4 * a * b - n * a - n * b;
					if (x > 0 && y > 0 && x % y == 0) {
						long c = x / y;
						Console.WriteLine($"{a} {b} {c}");
						return;
					}
				}
			}
		}
	}
}


Measured memory_bytes: 13140
<?php
$n = (int)trim(fgets(STDIN));
$map = [];
for ($i=0; $i < $n; $i++) { 
	$s = trim(fgets(STDIN));
	if (isset($map[$s])) {
		$map[$s] += 1;
	}else{
		$map[$s] = 1;
	}
}
arsort($map);
// var_dump($map);
$max = 0;
$out = [];
foreach ($map as $s => $c) {
	if ($c >= $max) {
		$out[] = $s;
		$max = $c;
	}else{
		break;
	}
}
natsort($out);
echo implode(PHP_EOL, $out);

Measured memory_bytes: 35316
#include <bits/stdc++.h>
using namespace std;
#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL);

int main() {
  FAST;
  int H1, H2, M1, M2, K, result;;
  cin >> H1 >> M1 >> H2 >> M2 >> K;
  result = (H2 * 60 + M2) - (H1 * 60 + M1) - K;
  cout << result << endl;
}

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

int main(){
	int m, f, r;
	
	while(1){
		cin>>m>>f>>r;
		if(m == -1 && f == -1 && r == -1) break;
		else if(m == -1 || f == -1)                         cout<<"F"<<endl;
		else if(80 <= m + f)                               cout<<"A"<<endl;
		else if(65 <= m + f && m + f < 80)     cout<<"B"<<endl;
		else if(50 <= m + f && m + f < 65)     cout<<"C"<<endl;
		else if(30 <= m + f && m + f< 50){
			if(r >= 50)                                 cout<<"C"<<endl;
			else                                            cout<<"D"<<endl;
		} else if(m + f < 30)                                cout<<"F"<<endl;
	}
	return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
#define SENTINEL 2000000000
typedef struct Card
{
    char suit;
    int value;
} Card;

Card L[MAX/2+2], R[MAX/2+2];

void Merge(Card A[], int left, int mid, int right)
{
    int p1 = mid - left;
    int p2 = right - mid;
    for (int i=0; i<p1; ++i) L[i] = A[left+i];
    for (int i=0; i<p2; ++i) R[i] = A[mid+i];
    L[p1].value = R[p2].value = SENTINEL;
    int i=0, j=0;
    for (int k=left; k<right; ++k) {
        if (L[i].value <= R[j].value) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
        }
    }
}
void MergeSort(Card A[], int left, int right)
{
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        MergeSort(A, left, mid);
        MergeSort(A, mid, right);
        Merge(A, left, mid, right);
    }
}
int Partition(Card A[], int p, int r)
{
    int i, j;
    Card x, t;
    i = p - 1;
    x = A[r];
    for ( j=p; j<r; ++j) {
        if (A[j].value <= x.value) {
            i++;
            t = A[i]; A[i] = A[j]; A[j] = t;
        }
    }
    t = A[i+1]; A[i+1] = A[r]; A[r] = t;
    return i + 1;
}
void QuickSort(Card A[], int p, int r)
{
    int q;
    if (p < r) {
        q = Partition(A, p, r);
        QuickSort(A, p, q-1);
        QuickSort(A, q+1, r);
    }
}
int main()
{
    int n, v;
    char s[5];
    Card A[MAX], B[MAX];
    int stable = 1;

    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> s >> v;
        A[i].suit = B[i].suit = s[0];
        A[i].value = B[i].value = v;
    }

    MergeSort(A, 0, n);
    QuickSort(B, 0, n-1);

    for (int i=0; i<n; ++i) {
        if (A[i].suit != B[i].suit) stable = 0;
    }

    if (stable == 1) cout << "Stable" << endl;
    else cout << "Not stable" << endl;

    for (int i=0; i<n; ++i) {
        cout << B[i].suit << " " << B[i].value << endl;
    }
    //for (int i=0; i<n; ++i)
      //  cout << A[i].suit << " " << A[i].value << endl;
    return 0;
}



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

int main() {
  string s; cin >> s;
  long long int cnt = 0, sum = 0;
  for (long long int i = 0; i < s.length(); i++) {
    if (s[i] == 'B')
      cnt++;
    else
      sum += cnt;
  }
  cout << sum << endl;
  return 0;
}


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

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i=0; i<N; i++) cin >> a.at(i);
    int K = 0;
    int i = 1;
    for (int j=0; j<N; j++) {
        if (a.at(j) == i) {
            K++;
            i++;
        }
    }
    if (K == 0) cout << -1 << endl;
    else cout << a.size() - K << endl;
}

Measured memory_bytes: 1152