akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
//long long
using ll = long long;
 
// pair<int, int>
using PII = pair<int, int>;
 
//最大値、mod
const int MOD = 1000000007;
const int INF = 1000000000;
const long long LINF = 1e18;
const int MAX = 510000;
 
//出力系
#define print(x) cout << x << endl
#define prints(x) cout << fixed << setprecision(10) << x << endl
#define printc(x) cout << setw(2) << setfill('0') << x << endl;
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()
 
//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
 
//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
 
// 最小公倍数
unsigned lcm(unsigned a, unsigned b){
    return a / gcd(a, b) * b; 
}
 
// a = max(a, b), a = min(a, b)
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; }
 
// 累乗(MODをとる)
ll pow_mod(ll num, ll pow, ll mod) {
    ll prod = 1;
    num %= mod;
    while (pow > 0) {
        if (pow & 1) prod = prod * num % mod;
        num = num * num % mod;
        pow >>= 1;
    }
    return prod;
}
 
 
 
// 二項係数(MODとる、1 ≦ k ≦ n ≦ 10^7 程度)
// COMinit()
// COM(x, y)
// とコンビで使う
 
// テーブルを作る前処理
long long 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;
}
 
int dx[4] = {1, 0, 0, -1}, dy[4] = {0, 1, -1 ,0};
 
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
 
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }
 
    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
 
    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }
 
    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};


bool f(string a){
    string t = a;
    reverse(all(a));
    return t == a;
}

int main(){
    string S;
    cin >> S;
    int N = S.length();
    string S2 = S.substr(0, N /2);
    if(f(S) && f(S2)) yes;
    else no;
    return 0;
}

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

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


void solve()
{  
    int l,r,d;
    cin>>l>>r>>d;
    
    int res=0;
    for(int i=l;i<r+1;i++)
    {
        if(i%d==0)
        res++;
    }
    cout<<res<<endl;
  
}


int main()
 {  fast();
    solve();
	return 0;
}

Measured memory_bytes: 3632
// D.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

int main(int argc, char *argv[]) {
	LL n;
	cin >> n;
	LL ans = ((n - 1) * n) / 2;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
nums = [int(i) for i in input().split()]

mod = 10 ** 9 + 7 # (modの値をすごく大きくすれば（5乗とか）、普通のnCrとして使える)
MAX = 10 ** 5 + 1 # これは変動するので注意。せいぜい10 ** 6くらいまでがTLEの限界

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

nums.sort()
MIN = 0
for i in range(n): #ここをkとして勘違いしていた。
    MIN += (nums[i] * nCr(n - i - 1, k - 1)) % mod

nums.sort(reverse=True)
MAX = 0
for i in range(n):
    MAX += (nums[i] * nCr(n - i - 1, k - 1)) % mod

ans = (MAX - MIN) % mod
print(ans)

Measured memory_bytes: 63344
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <queue>
#include <stack>
#include <string.h>
#include <list>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define all(a)  (a).begin(), (a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define rep(i,n) for(int i = 0; i < n; i++)
#define repR(i,n) for(int i = n-1; i >= 0; i--)
#define FOR(i,m,n) for(int i = m; i < n; i++)
#define PB push_back
#define MP make_pair
#define EPS (1e-7)
#define INF (1e12)
#define PI (acos(-1))

int main(){
    int a, b, k;
    cin >> a >> b >> k;
    if(b-a+1 <= 2*k){
        FOR(i,a,b+1) cout << i << endl;
    }
    else{
        FOR(i,a,a+k) cout << i << endl;
        FOR(i,b-k+1,b+1) cout << i << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DEBUG(x) cout << #x << " = " << x << endl
#define pb push_back
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
map <ll, ll> F_mem;
map <ll, ll> f_mem;

ll add(ll a, ll b)
{
    return (a + b) % MOD;
}

ll mult(ll a, ll b)
{
    return (a*b) % MOD;
}

ll f(ll N)
{
    if (f_mem.find(N) != f_mem.end())
    {
        return f_mem[N];
    }

    ll res;
    if (N == 0) res = 1;
    else if (N == 1) res = 1;
    else if (N % 2 == 1) res = f(N/2);
    else if (N % 2 == 0) res = add(f(N/2), f(N/2-1));

    return f_mem[N] = res;
}

ll F (ll N)
{
    if (F_mem.find(N) != F_mem.end())
    {
        return F_mem[N];
    }

    ll res;
    if (N == 0) res = 1;
    else if (N == 1) res = 2;
    else if (N % 2 == 1) res = add(mult(2,f(N/2)),mult(3,F(N/2-1)));
    else if (N % 2 == 0) res = add(f(N/2), mult(3,F(N/2-1)));

    return F_mem[N] = res;
}


int main()
{
    //freopen("input.txt", "r", stdin);
    ll N;
    cin >> N;
    cout << F(N);


    return 0;
}



Measured memory_bytes: 256
//This program is written by Brian Peng.
#pragma GCC optimize("Ofast","inline","no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Rd(a) (a=rd())
#define Gc(a) (a=getchar())
#define Pc(a) putchar(a)
int rd(){
	int x;char c(getchar());bool k;
	while(!isdigit(c)&&c^'-')if(Gc(c)==EOF)exit(0);
	c^'-'?(k=1,x=c&15):k=x=0;
	while(isdigit(Gc(c)))x=x*10+(c&15);
	return k?x:-x;
}
void wr(int a){
	if(a<0)Pc('-'),a=-a;
	if(a<=9)Pc(a|'0');
	else wr(a/10),Pc((a%10)|'0');
}
signed const INF(0x3f3f3f3f),NINF(0xc3c3c3c3);
long long const LINF(0x3f3f3f3f3f3f3f3fLL),LNINF(0xc3c3c3c3c3c3c3c3LL);
#define Ps Pc(' ')
#define Pe Pc('\n')
#define Frn0(i,a,b) for(int i(a);i<(b);++i)
#define Frn1(i,a,b) for(int i(a);i<=(b);++i)
#define Frn_(i,a,b) for(int i(a);i>=(b);--i)
#define Mst(a,b) memset(a,b,sizeof(a))
#define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
#define N (200010)
int n,k,a[N],r[N],b[N];
void mlt(int*a,int*b,int*r){Frn1(i,1,n)r[i]=b[a[i]];}
signed main(){
	Rd(n),Rd(k);
	Frn1(i,1,n)Rd(a[i]),r[i]=i;
	while(k){
		if(k&1)mlt(r,a,b),copy(b+1,b+n+1,r+1);
		mlt(a,a,b),copy(b+1,b+n+1,a+1),k>>=1;
	}
	wr(r[1]),exit(0);
}


Measured memory_bytes: 8320
#include"bits/stdc++.h"
using namespace std;

void Main() {
  int D;
  cin >> D;
  if (D==25) cout << "Christmas" << endl;
  else if (D==24) cout << "Christmas Eve" << endl;
  else if (D==23) cout << "Christmas Eve Eve" << endl;
  else cout << "Christmas Eve Eve Eve" << endl;
}

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

Measured memory_bytes: 256
import std.stdio, std.string, std.array, std.conv;

bool binarySearch(int n, int key, int[] x) {
    int l = 0, r = n, m;
    while (l < r) {
        m = (l + r) / 2;
        if (key == x[m]) return true;
        if (key < x[m]) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return false;
}

void main() {
    int n = readln.chomp.to!int;
    int[] s = readln.chomp.split.to!(int[]);
    int q = readln.chomp.to!int;
    int[] t = readln.chomp.split.to!(int[]);
    int cnt = 0;
    foreach (x; t) {
        if (binarySearch(n, x, s)) ++cnt;
    }
    cnt.writeln;
}


Measured memory_bytes: 6888
#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define RVSORT(v) sort(v.rbegin(), v.rend());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

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

int gcd(int a,int b){return b?gcd(b,a%b):a;}

ll modpow(ll n,ll k){
  if(k == 1){
    return n;
  }else if(k == 0){
    return 1;
  }else if(k%2==0){
    ll memo = modpow(n,k/2)%MOD;
    return memo*memo%MOD;
  }else{
    return n * modpow(n,k-1)%MOD;
  }
}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<int> num;  //連なってる個数（コンだけ）

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

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

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

    int getNum(int x){
      return num[root(x)];
    }

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


int main(){

  int H,W; cin>>H>>W;
  string s[H];

  REP(i,H){
    cin>>s[i];
  }

  UnionFind yoko[H](W);
  UnionFind tate[W](H);

  REP(i,H){
    REP(j,W){
      if(s[i][j] =='#'){
        yoko[i].setZero(j);
        tate[j].setZero(i);
      }else{
        if(j!=0){
          if(s[i][j-1]=='.'){
            yoko[i].unite(j-1,j);
          }
        }
        if(i!=0){
          if(s[i-1][j]=='.'){
            tate[j].unite(i-1,i);
          }
        }
      }
    }
  }

  ll ans = 0;
  REP(i,H){
    REP(j,W){
      if(s[i][j]=='.'){
        ans = max(ans,(ll)(yoko[i].getNum(j) + tate[j].getNum(i) - 1));
        //cout<<i<<"    "<<j<<"    "<<yoko[i].getNum(j)<<"   "<<tate[j].getNum(i)<<endl;
      }
    }
  }

  cout<<ans<<endl;


 

  return 0;
}

Measured memory_bytes: 67200
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<sstream>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=2e5+10;
const int inf=1e9;
int n;
char c[N];
vector<int>a;
set<int>b;
int main(){
	ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>n>>c+1;
	rep(i,1,n){
		if(c[i]=='W') a.pb(i);
		else b.insert(i);
	}
	int ans=0;
	for(int x:a){
		if(b.empty()) break;
		auto it=b.end();
		--it;
		if(*it>x){
			ans++;
			b.erase(it);
		}else break;
	}
	cout<<ans<<endl;
	return 0;
}
/*
WRWWRWRR
RRRWRWWW
*/

Measured memory_bytes: 13196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=2010;
const ll inf=2e17;

int n, A[MX];
ll B[MX], ans, x;
int pos[MX];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>x;
    for(int i=1; i<=n; i++) cin>>A[i];
    ll ans=0;
    for(int i=1; i<=n; i++)
        pos[i]=i, ans+=A[i];

    for(int d=1; d<n; d++){
        ll now=0;
        for(int i=1; i<=n; i++){
            int j=(i-d+n-1)%n+1;
            if(A[j]<A[pos[i]]) pos[i]=j;
            now+=A[pos[i]];
        }
        now+=x*d;
        ans=min(ans, now);
    }
    cout<<ans;
    return 0;
}

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

int main() {
    int n, v, j;
    cin >> n;

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

    for(int i = 0; i < n; i++) {
        cout << A.at(i);
        if(i == n - 1) {
            cout << endl;
        } else {
            cout << " ";
        }
    }

    for(int i = 1; i < n; i++) {
        v = A.at(i);
        j = i - 1;
        while(j >= 0 && A.at(j) > v) {
            A.at(j + 1) = A.at(j);
            j--;
        }
        A.at(j + 1) = v;

        for(int i = 0; i < n; i++) {
            cout << A.at(i);
            if(i == n - 1) {
                cout << endl;
            } else {
                cout << " ";
            }
        }
    }
}


Measured memory_bytes: 3072
#include <stdio.h>
  
#define MAX 9
  
int main(void)
{
  int i = 0;
  int j = 0;
    
  for ( i = 0; i < MAX; i++ ) {
 
    for ( j = 0; j < MAX; j++ ) {
 
      printf("%dx%d=%d\n", (i+1), (j+1), (i+1)*(j+1));
 
    }
    
  }
  
  return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d;
  int count1=0,count2=0;
  cin>>a>>b>>c>>d;
  while(c>0){
    c=c-b;
    count1++;
  }
  while(a>0){
    a=a-d;
    count2++;
  }//cout<<count1<<count2;
  if(count1>count2){
      cout<<"No";
  } 
  else {
      cout<<"Yes";
  }
  return 0;
}


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

int main()
{
    int n, q;
    cin >> n;
    vector<ll> a(101010, 0);
    ll sum = 0;
    rep(i,n)
    {
        int t;
        cin >> t;
        sum += t;
        a[t]++;
    }

    cin >> q;
    rep(i,q)
    {
        ll b, c;
        cin >> b >> c;
        sum = sum - b*a[b] + c*a[b];
        a[c] += a[b];
        a[b] = 0;
        cout << sum << "\n";
    }
    return 0;
}

Measured memory_bytes: 4024
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))

sm = [0, P[0]]
for pi in P[1:]:
    x = sm[-1] + pi
    sm.append(x)

# print(sm)

mx = 0
mxi = 0
for i in range(N-K+1):
    x = sm[i+K] - sm[i]
    # print(i, x)
    if x > mx:
        mx = x
        mxi = i

# print(mx, i)

ans = 0
for i in range(K):
    p = P[mxi+i]
    # print('p', p)
    ans += ((1 + p) * p / 2) / p
print(ans)

Measured memory_bytes: 25060
a,b,c,d=list(input())
import itertools
#長さ3の+と-の組み合わせができる　イテレータ
for ops in itertools.product(["+","-"],repeat=3):
    eq = a+ops[0]+b+ops[1]+c+ops[2]+d
    x = eval(eq)
    if x == 7:
        break

ans = eq + "=7"
print(ans)

Measured memory_bytes: 3060
#include<stdio.h>
#define MAX 100
#define WHITE 1
#define GREY 2
#define BLACK 3
#define NIL -1

int M[MAX][MAX],c[MAX],d[MAX],f[MAX],ts,n;
int queue[MAX],head=0,tail=0;

int deq(){
  head++;
  if(head==MAX){
    head=0;
    return queue[MAX-1];
  }
  return queue[head-1];
}
void enq(int u){
  queue[tail++]=u;
  if(tail==MAX) tail=0;
}

void bfs(){
  int i,u=0;
  for(i=0;i<n;i++){
    c[i]=WHITE;
    d[i]=NIL;
  }
  d[u]=0;
  c[u]=GREY;
  enq(u);

  while(head!=tail){
    u=deq();
    for(i=0;i<n;i++){
      if(M[u][i]==1&&c[i]==WHITE){
	enq(i);
	c[i]=GREY;
	d[i]=d[u]+1;
      }
    }
    c[u]=BLACK;
  }
}

int main(){
  int i,j,u,k,l;
  scanf("%d",&n);

  for(i=0;i<n;i++)
    for(j=0;j<n;j++) M[i][j]=0;

  for(i=0;i<n;i++){
    scanf("%d",&u);
    scanf("%d",&k);
    for(j=0;j<k;j++){
      scanf("%d",&l);
      M[u-1][l-1]=1;
    }
  }
  bfs();
  /*for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(j>0) printf(" ");
      printf("%d",M[i][j]);
    }
    printf("\n");
    }*/
  for(i=0;i<n;i++) printf("%d %d\n",i+1,d[i]);
  return 0;
}



Measured memory_bytes: 2108
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>


/* 
*    coder :: ATUL_PANDEY_2608
*        >>> INDIA <<<
*/
using namespace std;
using namespace __gnu_pbds;

// #define  part ..
#define pb(a) push_back(a)
#define all(a) a.begin(),a.end() 
#define mod 1000000007
//#define maxx 200006
#define ll long long 
#define quick    ios_base::sync_with_stdio(NULL),cin.tie(0);
#define listll vector< long long > 
#define listi vector< int> 
#define pii   pair<int , int> 
#define pll pair<long long , long long > 
#define minheap priority_queue<long long , vector< long long >, greater<long long > >
#define rep(i,a,b) for(int i=a;i<b;i++)
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}


template < class T > using oset = tree< T , null_type, less  < T  > , rb_tree_tag , tree_order_statistics_node_update > ;


// end of #define 

// define globals ...
const int maxx = 2e5+26;

//write function from here ...







int Main(){

int n;
cin>>n;



listll arr;
for(int i=0;i<n;i++)
{
	ll a;
	cin>>a;
	arr.pb(a);
}

ll ans = 0;

for(int i=0;i<n;i++)
{
	for(int j=i+1;j<n;j++)
	{
		for(int k=j+1;k<n;k++){
			
			if( (arr[i]+arr[j]>arr[k] )&& (arr[i]+arr[k]>arr[j] )&&  (arr[k]+arr[j]>arr[i])&& arr[i]^arr[j] &&arr[i]^arr[k]&&arr[j]^arr[k] )

			ans+=1;
			
			
			
		}
	}
}

cout<<ans<<endl;


return 0;

}

















int main(){
 quick;
int t =1; 
//cin>>t;
while(t-- )
 Main();

 return 0;


}


Measured memory_bytes: 3672
#include<iostream>
using namespace std;
int main() {
int x,y;cin >> x >> y;
int xmin,xmax,ymax,ymin;
xmin = ymin = 0;xmax = ymax = 1;
bool f = 1;int i;
for(i=0;f;i++) {
if(xmin<=x&&x<xmax&&ymin<=y&&y<ymax)f = 0;
if(i%4==0)xmax+=ymax-ymin;
else if(i%4==1)ymax+=xmax-xmin;
else if(i%4==2)xmin+=ymin-ymax;
else ymin+=xmin-xmax;
}
cout << (i-1)%3+1 << endl;
}


Measured memory_bytes: 3108
n=int(input())
digit = len(str(n))+1
th_adic = [0]*digit
mask = [0,3,5,7]

def number():
  ret=0
  d=1
  for i in range(digit):
    ret+=d*mask[th_adic[i]]
    d*=10
  return ret

def appear357():
  return (1 in th_adic) and (2 in th_adic) and (3 in th_adic)

def inc():
  for i in range(digit):
    if th_adic[i] == 3:
      th_adic[i]=1
      continue
    th_adic[i]+=1
    break

ret=0
while number()<=n:
  if appear357():
    ret+=1
  inc()
print(ret)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define mk make_pair
#define pb push_back
#define eps 1e-12
#define MAXN 200009
using namespace std;
inline ll answer(ll h,ll w)
{
	ll temp1=h;
	ll temp2=w;
	ll p=(temp1/3);
	p++;
	ll maxx=p*w;
	temp1=temp1-p;
	temp1/=2;
	ll minn=temp1*w;
	ll fans=maxx-minn;
	temp2/=2;
	temp1=h-p;
	ll ntemp=maxx;
	maxx=max(maxx,(temp2*temp1));
	minn=min(ntemp,(temp2*temp1));
	if(w%2)
	{
		maxx=max(maxx,(temp1*(temp2+1)));
	}
	fans=min(fans,abs(maxx-minn));
	ll ttemp1=h;
	ll ttemp2=w;
	ll pp=(h/3);
	ll maxx1=pp*w;
	ll minn1;
	ttemp2/=2;
	ttemp1=h-pp;
	ntemp=maxx1;
	maxx1=max(maxx1,(ttemp2*ttemp1));
	minn1=min(ntemp,(ttemp2*ttemp1));
	if(w%2)
	{
		maxx1=max(maxx1,(ttemp1*(ttemp2+1)));
	}
	//cout<<maxx1<<" "<<minn1<<"\n";
	fans=min(fans,abs(maxx1-minn1));
	return fans;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll h,w;
	cin>>h>>w;
	if((h%3==0)||(w%3==0))
	{
		cout<<0<<"\n";
	}
	else if(h==2||w==2)
	{
		cout<<"1\n";
	}
	else
	{
		ll fans1=answer(h,w);
		fans1=min(fans1,answer(w,h));
		cout<<fans1<<"\n";
	}
}

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

using namespace std;

int main() {
  int N, t{};
  cin >> N;
  vector<int> a(N);
  for (auto &e : a) {
    cin >> e;
    t += e;
    e *= N;
  }
  cout << min_element(begin(a), end(a),
                      [&](int x, int y) { return abs(t - x) < abs(t - y); }) -
              begin(a)
       << endl;

  return 0;
}


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

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

  vector<int> v(N),w(N);
  for (int i = 0; i < N; i++)
  {
    cin >> v[i] >> w[i];
  }

  vector<vector<int>> dp(N+1,vector<int>(W+1));
  for (int i = 1; i <= N; i++)
  {
    for (int j = 0; j <= W; j++)
    {
      if(w[i-1] <= j){
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
      }
      else dp[i][j] = dp[i-1][j];
    }
  }
  cout << dp[N][W] << endl;
}


Measured memory_bytes: 6848
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<string>

#define rep(i,p) for(long long int i=0;i<p;i++)
#define reep(i,p) for(long long int i=1;i<=p;i++)
#define ll long long

using namespace std;

int main(){

ll int X;
cin >> X;

if(X>=30){
	cout << "Yes";
}
else{
	cout << "No";
}











	return 0;

}



Measured memory_bytes: 3592
#include <bits/stdc++.h>
//#define local
#ifdef local
    #include "dbg-macro/dbg.h"
#endif
//#define hacks
#ifdef hacks
    #include <boost/multiprecision/cpp_int.hpp>
#endif
#define p std::pair
#define ll long long
#define ld long double
#define ull unsigned long long
#define pi std::pair<int, int>
#define mp std::make_pair
#define stdabs std::abs
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (unsigned long long i = 0; i < (unsigned long long)(n); ++i)
#define vec std::vector
#define oreq |=
#define npm next_permutation
using namespace std;
std::vector<unsigned ll> genprimevec(const unsigned ll N);
ll extgcd(ll a, ll b, ll& x, ll& y);
ll nCr(ll n, ll r);
void stat();
template <typename T> T fact(T num);
constexpr ll mod = 1000000000 + 7;
int main()
{
    stat();
    unordered_map<string, int> map;

    int n;
    cin >> n;
    string s;
    rep(i, n)
    {
        cin >> s;
        if (map.count(s) == 0) { map.insert(mp(s, 0)); }
        else {
		 ++map.at(s);
		

        }

    }
    vec<string> ans;
    int maxc = 0;
    for (auto const& st : map) {
        maxc = max(maxc, st.second);
    }
#ifdef local
    dbg(maxc);
#endif
    for (auto const& st : map) {
        if (st.second == maxc) { ans.push_back(st.first); }
    }
    sort(all(ans));
    for (const auto& a : ans) {
        cout << a << endl;
    }
    return 0;
}
ll extgcd(ll a, ll b, ll& x, ll& y)
{
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}


std::vector<unsigned ll> genprimevec(const unsigned ll N)
{
    std::vector<bool> is_prime(N + 1);
    for (unsigned ll i = 0; i <= N; i++) {
        is_prime[i] = true;
    }
    std::vector<unsigned ll> P;
    for (unsigned ll i = 2; i <= N; i++) {
        if (is_prime[i]) {
            for (unsigned ll j = 2 * i; j <= N; j += i) {
                is_prime[j] = false;
            }
            P.emplace_back(i);
        }
    }
    return P;
}

void stat(){
#ifdef local
    rep(i, 2){std::cout << "local enable" << std::endl;
}
#endif
#ifdef hacks
rep(i, 2) { std::cout << "boost enable" << std::endl; }
#endif
}

ll nCr(ll n, ll r)
{
    ll num = 1;
    for (ll i = 1; i <= r; i++) {
        num = num * (n - i + 1) / i;
    }
    return num;
}

template <typename T> T fact(T num)
{
    if (num == 1) { return 1; }
    return num * fact(num - 1);
}


Measured memory_bytes: 26972
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

const int MAX = 1000000;
const int MOD = 1000000007;

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;
}

int main(){
  int x, y; cin >> x >> y;
  COMinit();
  if((x+y)%3) cout << 0 << endl;
  else{
    int prev = (x+y)/3; x-=prev; y-=prev;
    cout << COM(x+y, y) << endl;
  }
}     
      

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

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define fi first
#define se second

#define INF 2147483600

// Range Minimum Query
class RMQ {
private:
  int n;
  vector<int> data;
  vector<int> pos;
public:
  RMQ(int n_){
    n=1;
    while(n<n_) n*=2;
    data = vector<int>(2*n-1, INF);
    pos  = vector<int>(2*n-1, -1);
  }
  void update(int k, int a){ // update data[k]=a, k(0-indexed)
    k+=n-1;
    data[k]=a;
    pos[k] =k-n+1;
    while(k>0){
      k = (k-1)/2;
      if(data[k*2+1]<data[k*2+2]){
        data[k] = data[k*2+1];
        pos[k]  = pos[k*2+1];
      } else {
        data[k] = data[k*2+2];
        pos[k]  = pos[k*2+2];
      }
    }
  }
  pair<int,int> query(int a,int b,int k=0,int l=0,int r=-1){ //min value in [a,b)
    if(r==-1) r=n;
    // k := current node, range of k := [l,r)
    if(r<=a || b<=l) return mp(INF,-1);
    if(a<=l && r<=b) return mp(data[k],pos[k]);
    pair<int,int> vl=query(a,b,k*2+1,l,(l+r)/2);
    pair<int,int> vr=query(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
  }
  inline int operator[](int idx){ return data[idx+n-1]; }
}; // END class RMQ

RMQ rmq(1);

// 閉区間[l,r]
long search(int l, int r){
  if(l>r) return 0;
  if(l==r) return rmq[l];

  int pos = rmq.query(l,r+1).se;

  return search(l, pos-1) + search(pos+1,r) + (long)(pos-l+1)*(r-pos+1)*rmq[pos];
}

int main(){
  int n;
  cin>>n;
  rmq = RMQ(n);
  rep(i,n){
    int d;
    scanf("%d", &d);
    rmq.update(i,d);
  }

  long res = search(0,n-1);

  cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 48128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(), (x).end()
#define fsp(x) cout << fixed << setprecision(x)
const ll inf = LLONG_MAX;
const long double pi = M_PI;
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}

int main() {
  ll r;
  cin >> r;
  cout << 3 * r * r << endl;
}

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

ll X,Y,Z,K,a,b,c,cnt;
vector<ll> A(1000),B(1000),C(1000);
typedef tuple<ll,ll,ll,ll> Cake;
priority_queue<Cake> Q;
map<Cake,bool> used;

int main(void){
    cin >> X >> Y >> Z >> K;
    rep(i,X)cin >> A[i];
    rep(i,Y)cin >> B[i];
    rep(i,Z)cin >> C[i];
    sort(A.begin(),A.end(),greater<ll>());
    sort(B.begin(),B.end(),greater<ll>());
    sort(C.begin(),C.end(),greater<ll>());
    
    Cake cake = make_tuple(A[0]+B[0]+C[0],0,0,0);
    Q.push(cake);
    used[cake] = true; 
    while(cnt < K){
        cake = Q.top();Q.pop();
        a = get<1>(cake);
        b = get<2>(cake);
        c = get<3>(cake);
        if(a<X-1 && !used[make_tuple(A[a+1]+B[b]+C[c],a+1,b,c)]){
            Q.push(make_tuple(A[a+1]+B[b]+C[c],a+1,b,c));
            used[make_tuple(A[a+1]+B[b]+C[c],a+1,b,c)]=true;
        }
        if(b<Y-1 && !used[make_tuple(A[a]+B[b+1]+C[c],a,b+1,c)]){
            Q.push(make_tuple(A[a]+B[b+1]+C[c],a,b+1,c));
            used[make_tuple(A[a]+B[b+1]+C[c],a,b+1,c)] = true;
        }
        if(c<Z-1 && !used[make_tuple(A[a]+B[b]+C[c+1],a,b,c+1)]){
            Q.push(make_tuple(A[a]+B[b]+C[c+1],a,b,c+1));
            used[make_tuple(A[a]+B[b]+C[c+1],a,b,c+1)] = true;
        }
        cnt++;
        cout << get<0>(cake) << endl;
    }
    
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  string s,t;
  cin>>s>>t;
  int ans=1e9;
  for(int i=0;i<s.size();i++){
    int temp=0;
    int ji=0;
    for(int j=i;j-i<t.size();j++){
      if(j>=s.size()){
        temp=1e9;
        break;
      }
      if(s[j]!=t[ji]){
        temp++;
      }
      ji++;
    }
    ans=min(ans,temp);
    //cout<<temp<<endl;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3656
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define cool ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
#define MAX 1000001
#define mod 1000000007
#define pie 3.14159265358979323846
void solve()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	int i,c=0;
	char prev='1';
	for(i=0;i<s.size();i++){
		if(s[i]==prev){
			continue;
		}
		else{
			c++;
			prev=s[i];
		}
	}
	cout<<c;
}
int main()
{ 
    cool;
    int t;
    //cin>>t;
    t=1;
    while(t--){
    	solve();
	}
    return 0;
}


Measured memory_bytes: 3764
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <math.h>
#include <iomanip>
#include <queue>
#define inp(X) cin >> X
#define out(X) cout << X << endl
#define rep(i,n) for(int i=0;i<n;i++ )
#define rep2(i,f,n) for(int i=f;i<n;i++ )
#define MAX(A) *max_element(A.begin(),A.end())
#define MIN(A) *min_element(A.begin(),A.end())
#define SORT(A) sort(A.begin(),A.end())
using namespace std;

typedef long long int ll;
#define MOD 1000000007
#define INF 1000000001

ll gcd(ll x, ll y){
	if(y==0) return x;
	return gcd(y,x%y);
}

bool bfs(vector<vector<int>> g, vector<int> &dist, int sv)
{
	queue<int> q;
	q.push(sv);
	dist[sv]=0;
	while(!q.empty()){
		int now = q.front(); q.pop();
		for(auto v : g[now]){
			if(dist[v]!=-1) continue;
			dist[v] = dist[now]+1;
			q.push(v);
		}
	}
}

int main(void) {
	int n,x; cin >> n >> x;
	vector<int> l;
	rep(i,n){
		int a; cin >> a;
		l.push_back(a);
	}
	int d = 0;
	int ret = 0;
	while(d<=x){
		d += l[ret];
		ret++;
		if(ret>n) break;
	}
	out(ret);
}




Measured memory_bytes: 256
import sys

s = list(input())
ans = 0
point = 0

if s[len(s)-1] == "<":
    s.append(">")

def walk(n):
    sum = 0
    i = n
    l = len(s)
    while True:
        sum += 1
        if i+1 < l:
            if s[i] != s[i+1]:
                break
        else:
            break
        i += 1
    return sum

def sigma(n):
    return n*(n+1)//2

if s[0] == ">":
    point = walk(0)
    ans += sigma(point)

if point == len(s):
    print(ans)
    sys.exit()

while True:
    d1 = walk(point)
    point += d1
    ans += sigma(d1-1)
    d2 = walk(point)
    point += d2
    ans += max(d1,d2)
    ans += sigma(d2-1)
    if point == len(s):
        break

print(ans)

Measured memory_bytes: 94044
#include<stdio.h>
int main(void){
int W,H,x,y,r;
	
	scanf("%d",&W);
	scanf("%d",&H);
		scanf("%d",&x);
		scanf("%d",&y);
		scanf("%d",&r);
		
		if(W>=x+r && H>=y+r && 0<=x-r && 0<=y-r){
		printf("Yes\n");
		}
		else{
			printf("No\n");
		}
		return 0;
	}

Measured memory_bytes: 580
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect
import functools

def InsertionSort(A):
    for i in range(1,len(A)):
        key = A[i]
        j = i - 1
        while j>=0 and A[j]>key:
            A[j+1] = A[j]
            j-=1
        A[j+1] = key
        print(*A)
n = int(input())
A = list(map(int,input().split()))
print(*A)
InsertionSort(A)



Measured memory_bytes: 6712
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n, d, a;
    cin >> n >> d >> a;
    vp xh(n);
    rep(i, n) {
        int x, h;
        cin >> x >> h;
        xh[i] = P(x, h);
    }
    sort(xh.begin(), xh.end());
    
    vector<ll> range;
    vector<ll> bomb;
    bomb.pb(0);
    ll cnt = 0;
    for (auto p : xh) {
        int now_x = p.fi;
        int now_h = p.se;
        int idx = lower_bound(range.begin(), range.end(), now_x) - range.begin();
        if (idx != sz(range)) {
            now_h -= a * (bomb[sz(bomb) - 1] - bomb[idx]);
        }
        if (now_h <= 0) continue;
        bomb.pb((now_h + (a-1)) / a);
        cnt += bomb.back();
        bomb[sz(bomb) - 1] += bomb[sz(bomb) - 2];
        range.pb(now_x + 2*d);
    }
    cout << cnt << endl;
}

Measured memory_bytes: 5220
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		char[][] C = new char[2][3];
		Scanner sc = new Scanner(System.in);
		String a = sc.nextLine();
		String b = sc.nextLine();

		C[0][0] = a.charAt(0);
		C[0][1] = a.charAt(1);
		C[0][2] = a.charAt(2);
		C[1][0] = b.charAt(0);
		C[1][1] = b.charAt(1);
		C[1][2] = b.charAt(2);

		if(C[0][0]==C[1][2]&&C[0][1]==C[1][1]&&C[0][2]==C[1][0]&&C[1][0]==C[0][2]&&C[1][1]==C[0][1]&&C[1][2]==C[0][0]) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}


Measured memory_bytes: 21972
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    boolean tmp = true;

    while(tmp){
      String s = sc.next();
      int ans = 0;

      if(s.equals("0")){
        tmp = false;
        break;
      }

      for(int i = 0; i < s.length(); i++){
        ans += s.charAt(i) - '0';
      }

      System.out.println(ans);
    }
  }
}



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

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

pair<ll, ll> p[100005];

int main() {
	int n; cin >> n;
	rep(i, 0, n) cin >> p[i].first >> p[i].second;
	sort(p, p + n);
	cout << p[n - 1].first + p[n - 1].second << endl;
}


Measured memory_bytes: 1920
#include <stdio.h>

#define MAX 10000

typedef struct {
  int p;
  int left;
  int right;
} Node;

Node tree[MAX];
int n;

void preparse(int);   /* 先行順巡回 */
void inparse(int);    /* 中間順巡回 */
void postparse(int);  /* 後行順巡回 */

int main()
{
  int i, v, left, right, root;

  scanf("%d", &n);
  for(i=0; i<n; i++) {
    tree[i].p = -1;
  }
  for(i=0; i<n; i++) {
    scanf("%d %d %d", &v, &left, &right);
    tree[v].left = left;
    tree[v].right = right;
    if(left != -1)
      tree[left].p = v;
    if(right != -1)
      tree[right].p = v;
  }
  for(i=0; i<n; i++) {
    if(tree[i].p == -1)
      root = i;
  }

  printf("Preorder\n");
  preparse(root);
  printf("\nInorder\n");
  inparse(root);
  printf("\nPostorder\n");
  postparse(root);
  printf("\n");

  return 0;
}

void preparse(int u)
{
  if(u == -1)
    return ;
  printf(" %d", u);
  preparse(tree[u].left);
  preparse(tree[u].right);
}

void inparse(int u)
{
  if(u == -1)
    return ;
  inparse(tree[u].left);
  printf(" %d", u);
  inparse(tree[u].right);
}

void postparse(int u)
{
  if(u == -1)
    return ;
  postparse(tree[u].left);
  postparse(tree[u].right);
  printf(" %d", u);
}

Measured memory_bytes: 616
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring> 
#include<cassert>
#include<cmath>
#include<sstream>
#include<fstream>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
using namespace std;
vector<pair<int,long long> > nei[100005];
int n,m,s,t;
long long dis1[100005],dis2[100005];
void dij()
{
	priority_queue<pair<long long,int> > q1;
	q1.push(make_pair(0,s));
	
	memset(dis1,-1,sizeof(dis1));dis1[s]=0;
	while(!q1.empty())
	{
		long long d=q1.top().first;
		int x=q1.top().second;
		q1.pop();
		for(int i=0;i<nei[x].size();i++)
		{
			if(dis1[nei[x][i].first]<=-d+nei[x][i].second&&dis1[nei[x][i].first]!=-1) continue;
			dis1[nei[x][i].first]=-d+nei[x][i].second;
			q1.push(make_pair(d-nei[x][i].second,nei[x][i].first));
		}
	}
	
	
	priority_queue<pair<long long,int> > q2;
	q2.push(make_pair(0,t));
	memset(dis2,-1,sizeof(dis2));dis2[t]=0;
	while(!q2.empty())
	{
		long long d=q2.top().first;
		int x=q2.top().second;
		q2.pop();
		for(int i=0;i<nei[x].size();i++)
		{
			if(dis2[nei[x][i].first]<=-d+nei[x][i].second&&dis2[nei[x][i].first]!=-1) continue;
			dis2[nei[x][i].first]=-d+nei[x][i].second;
			q2.push(make_pair(d-nei[x][i].second,nei[x][i].first));
		}
	}
}
long long dp1[100005],dp2[100005];
long long dfs1(int v)
{
	if(dp1[v]!=-1) return dp1[v];
	dp1[v]=0;
	for(int i=0;i<nei[v].size();i++)
	{
		if(dis1[v]+nei[v][i].second==dis1[nei[v][i].first])
		{
			dp1[v]+=dfs1(nei[v][i].first);
			dp1[v]%=1000000007;
		}
	}
	return dp1[v];
}
vector<pair<int,int> >res;
long long dfs2(int v)
{
	if(dp2[v]!=-1) return dp2[v];
	dp2[v]=0;
	for(int i=0;i<nei[v].size();i++)
	{
		if(dis2[v]+nei[v][i].second==dis2[nei[v][i].first])
		{
			dp2[v]+=dfs2(nei[v][i].first);
			if(dis2[v]<dis1[v]&&dis2[nei[v][i].first]>dis1[nei[v][i].first]) res.push_back(make_pair(v,nei[v][i].first));
		//	if(dis2[v]*2==dis) res.push_back(make_pair(v,v));
			dp2[v]%=1000000007;
		}
	}
	return dp2[v];
}
long long mul(long long x)
{
	return x*x%1000000007;
}
int main()
{
	cin>>n>>m>>s>>t;
	s--,t--;
	for(int i=0;i<m;i++)
	{
		int u,v;
		long long d;
		cin>>u>>v>>d;
		u--,v--;
		nei[u].push_back(make_pair(v,d));
		nei[v].push_back(make_pair(u,d));
	}
	dij();
	memset(dp1,-1,sizeof(dp1));
	memset(dp2,-1,sizeof(dp2));
	dp1[t]=1;
	dp2[s]=1;
	dfs1(s);
	dfs2(t);
	for(int i=0;i<n;i++)if(dis1[i]*2==dis1[t]) res.push_back(make_pair(i,i));
	long long ans=mul(dp1[s]);
	for(int i=0;i<res.size();i++)
	{
		ans=ans-mul((1ll*dp1[res[i].first]*dp2[res[i].second])%1000000007);
		ans%=1000000007;
		if(ans<0) ans+=1000000007;
	}
	cout<<ans;
}

Measured memory_bytes: 25508
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef ::std::int_fast64_t i64;
typedef ::std::uint_fast64_t u64;
typedef ::std::int_fast32_t i32;
typedef ::std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(::std::istream& is, ::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    vector.reserve(size);
    ::std::copy_n(::std::istream_iterator<T>(is), size, ::std::back_inserter(vector));
  }
  template <typename T>
  void read(::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    ::tools::read(::std::cin, vector, size);
  }

  template <typename T, ::std::size_t N>
  void read(::std::istream& is, ::std::array<T, N>& array) {
    ::std::copy_n(std::istream_iterator<T>(is), N, array.begin());
  }
  template <typename T, ::std::size_t N>
  void read(::std::array<T, N>& array) {
    ::tools::read(::std::cin, array);
  }
}

#endif

// main.cpp



int main() {
  i64 N;
  std::cin >> N;
  std::vector<i64> A;
  tools::read(A, N);

  if (std::any_of(A.begin(), A.end(), [](const i64& A_i) { return A_i == 0; })) {
    std::cout << 0 << std::endl;
  } else {
    // Given x > 0 and y > 0,
    // x * y > 10 ** 18
    // x * y > quo(10 ** 18, y) * y + mod(10 ** 18, y)
    // x > quo(10 ** 18, y) + mod(10 ** 18, y) / y

    // Since 0 <= mod(10 ** 18, y) / y < 1, the equiation can simplify as follows.
    // x > quo(10 ** 18, y)
    std::cout << std::accumulate(A.begin(), A.end(), static_cast<i64>(1), [](const i64& prod, const i64& A_i){ return prod == -1 ? -1 : prod > 1000000000000000000 / A_i ? -1 : prod * A_i; }) << std::endl;
  }

  return 0;
}

Measured memory_bytes: 3984
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> a(n+2);
	rep(i,n) cin >> a.at(i+1);
	int ans=0;
	rep(i,n+1) ans+=abs(a.at(i)-a.at(i+1));
	for(int i=1;i<=n;++i){
		cout << ans-abs(a.at(i-1)-a.at(i))-abs(a.at(i)-a.at(i+1))+abs(a.at(i-1)-a.at(i+1)) << endl;
	}
}

Measured memory_bytes: 1664
#include <cstring>
#include <cstdio>
#define MOD 1000000007
char str[100005];
int dp[100005], nxt[100005][5], pre[100005];
int main()
{
	// freopen("AGC027-E.in", "r", stdin);
	scanf("%s", str);
	int n = strlen(str);
	bool flg = true;
	for (int i = 1; i < n; i++)
		flg &= str[i] != str[i - 1];
	if (flg)
	{
		puts("1");
		return 0;
	}
	for (int i = 0; i < n; i++)
		pre[i] = ((i ? pre[i - 1] : 0) + (str[i] - 'a') + 1) % 3;
	nxt[n][0] = nxt[n][1] = nxt[n][2] = n;
	for (int i = n - 1; i >= 0; i--)
	{
		memcpy(nxt[i], nxt[i + 1], sizeof(nxt[i]));
		nxt[i][pre[i]] = i;
	}
	dp[0] = 1;
	for (int i = 0; i < n; i++)
	{
		int x = i ? pre[i - 1] : 0, pos = nxt[i][(x + 1) % 3];
		if (pos < n)
			(dp[pos + 1] += dp[i]) %= MOD;
		pos = nxt[i][(x + 2) % 3];
		if (pos < n)
			(dp[pos + 1] += dp[i]) %= MOD;
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		if (pre[i] == pre[n - 1])
			(ans += dp[i + 1]) %= MOD;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 2944
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int H,W,h,w;
    cin >> H >> W >> h >> w;
    cout << (H - h) * (W - w) << endl;
}

Measured memory_bytes: 764
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
	int n, a;
	cin >> n;
	vector<int> slime(n);
	for (int i = 0; i < n; ++i) cin >> slime[i];

	int ans = 0;
	for (int i = 0; i < n - 1; ++i) {
		if (slime[i] == -1) continue;
		if (slime[i] == slime[i + 1]) {
			slime[i + 1] = -1;
			++ans;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
	ll n,c=0;
	// c is count of pairs before taking new input
	// map second value is occurence of that string previously
	cin>>n;
	unordered_map<string,int> m;
	string s;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		sort(s.begin(),s.end());
		c+=m[s]; // 2 strings=1 pair
		m[s]++;
		
		
	}
	cout<<c;
	
	
}

Measured memory_bytes: 10660
a,b,c = map(int,input().split())
k = int(input())

while k>0 and b <= a:
    b*=2
    k-=1
while k>0 and c <=b:
    c*=2
    k-=1
if a <b and b<c:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9136
#include <stdio.h>

int main(){
	int count = 0, m[1000], f[1000], r[1000], i;
	
	for (i = 0; i < 1000; i++){
		scanf("%d%d%d", &m[i], &f[i], &r[i]);
		if (m[i] == -1 && f[i] == -1 && r[i] == -1){
			break;
		}
		count++;
	}
	
	for (i = 0; i < count; i++){
		if (m[i] == -1 || f[i] == -1){
			printf("F\n");
		}
		else if (m[i] + f[i] >= 80){
			printf("A\n");
		}
		else if (m[i] + f[i] >= 65){
			printf("B\n");
		}
		else if (m[i] + f[i] >= 50){
			printf("C\n");
		}
		else if (m[i] + f[i] >= 30){
			(r[i] >= 50)? printf("C\n"): printf("D\n");
		}					
		else{
			printf("F\n");
		}
	}
	return 0;
}

Measured memory_bytes: 592
# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
dxdy=((1,0),(0,1))
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

def resolve():
    N,=pin()
    print(pow(N,3)/27)
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
if __name__=="__main__":resolve()


Measured memory_bytes: 38384
import java.util.Scanner;
import java.util.Vector;

public class Main {

	public static void main(String[] args) {
		doIt();
	}
	
	public static void doIt(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		while(n + m > 0){
			Vector<Integer> v = new Vector<Integer>(n);
			for(int i = 0; i < n; i++){
				v.add(i + 1);
			}
			int point = 0;
			for(int i = n; i > 1; i--){
				point = (point + m - 1) % i;
				//System.out.println("point = " + point + ", v[point] = " + v.elementAt(point));
				v.remove(point);
			}
			System.out.println(v.get(0));
			n = sc.nextInt();
			m = sc.nextInt();
		}
	}
}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	bool flag=0;
	getline (cin,s);
	for(int i=0;i<s.length();i++){
		if(s[i]=='C')flag=1;
		if(flag&&s[i]=='F'){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

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

#define rep(i,n) for(ll i = 0; i < n; i++)
#define per(i,n) for(ll i = n-1; i >= 0; i--)
#define REP(i,n) for(ll i = 1; i < n; i++)
#define PER(i,n) for(ll i = n; i >= 1; i--)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
using vP = vector<P>;
using vPP = vector<vP>;
using vPl = vector<Pl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const ll mod = 1e9+7;

long long Modpow(long long a, int n){
  if(n == 0) return 1;
  if(n%2 == 0){
    long long res = Modpow(a, n/2);
    return res * res % mod;
  }
  return a * Modpow(a, n-1) % mod;
}

int inv(int n) { // 逆元
  return Modpow(n, mod-2);
}

struct Combination { 
  vector<long long> fact, ifact;
  Combination(int n):fact(n+1), ifact(n+1) {
    fact[0] = 1;
    for(long long i = 1; i <= n; i++) fact[i] = fact[i-1]*i % mod;
    ifact[n] = inv(fact[n]);
    for(long long i = n; i >= 1; i--) ifact[i-1] = ifact[i]*i % mod;
  }
  long long operator()(int n, int k) { // modcom (nCk % mod)
    if(k < 0 || k > n) return 0;
    return ((fact[n] * ifact[k]) % mod * ifact[n-k]) % mod;
  }
};

int main(){
  ll n, k;
  cin >> n >> k;
  Combination c(n);
  for(ll i = 1; i <= k; i++) {
    ll ans = (c(n-k+1, i) % mod) * c(k-1, i-1) % mod;
    cout << ans << endl;
  }
}

Measured memory_bytes: 3612