akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
k = I()
d = deque([1,2,3,4,5,6,7,8,9])
for i in range(k):
    num = d.popleft()
    if num%10 != 0:
        d.append(10*num + (num%10) -1)
    d.append(10*num + (num%10))
    if num%10 != 9:
        d.append(10*num + (num%10) + 1)
print(num)

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

int main(){
  ll n;
  cin >> n;
  ll goukei=0;
  for(ll i=1;i<=n;++i){
    goukei+=i;
    if(goukei>=n){
      for(ll j=i;j>=1;--j){
        if(n-j>=0){
          n-=j;
          cout << j << endl;
        }
      }
      return 0;
    }

  }
}


Measured memory_bytes: 256
import sys

input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))
    Ep = [(x+1)/2 for x in p]


    base = sum(Ep[:K])
    ans = base
    for i in range(N-K):
        base -= Ep[i]
        base += Ep[i+K]
        ans = max(ans, base)
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 24404
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define int long long
#define pb push_back
#define x first
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
const int INF = 1e9, MOD = 1e9 + 7; /// think
const ll LINF = 1e18;


const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
inline bool inside (int x, int y, int n, int m) {
    return 0 <= x && 0 <= y && x < n && y < m;
}

template<class T> bool umin (T &a, T b) {return a > b ? (a = b, true) : false; }
template<class T> bool umax (T &a, T b) {return a < b ? (a = b, true) : false; }


main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector <int> a(n), b(m);
    for (auto &i : a) cin >> i;
    for (auto &j : b) cin >> j;
    int ans = 0, j = 0;
    ll sum = 0;
    for (auto &i : a) sum += i;
    for (int i = n - 1; i >= 0; i--) {
        while (j < m && sum + b[j] <= k) {
            sum += b[j];
            ++j;
        }
        if (sum <= k) umax(ans, i + 1 + j);
        sum -= a[i];
    }
    while (j < m && sum + b[j] <= k) {
        sum += b[j];
        ++j;
    }
    if (sum <= k) {
        umax(ans, j);
    }
    cout << ans << '\n';
}


Measured memory_bytes: 4784
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using ll=long long;
#define rep(i,a,b) for(ll i=a;i<ll(b);i++)
#define repr(i,a,b) for(ll i=a;i>=ll(b);i--)
#define endl "\n"
#define ALL(x) x.begin(),x.end()
#define ALLR(x) x.rbegin(),x.rend()
#define INF 1e9
#define DEBUG(x) cout<<"debug: "<<x<<endl
using namespace std;

int n,x,t,ans;
int main() {
	cin>>n>>x>>t;
	int a = n%x;
	if(a==0) ans = n/x*t;
	else ans= ((n/x)+1)*t;
	cout << ans<< endl;
    return 0;
}

Measured memory_bytes: 3196
#include<iostream>
int N, L;
int A[100010];
int last;
int main() {
	std::cin >> N >> L;
	for (int i = 0; i < N; i++) {
		std::cin >> A[i];
	}
	for (int i = 1; i < N; i++) {
		if (A[i] + A[i - 1] >= L) {
			last = i;
			break;
		}
	}
	if (!last) {
		std::cout << "Impossible" << std::endl;
		return 0;
	}
	std::cout << "Possible" << std::endl;
	for (int i = 1; i < last; i++) {
		std::cout << i << std::endl;
	}
	for (int i = N - 1; i > last; i--) {
		std::cout << i << std::endl;
	}
	std::cout << last << std::endl;
	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <memory>
#include <memory.h>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool g[40][40][40][40];
int memo[40][40];

int main(){
  int w, h;
  int can;
  while(cin >> w >> h && (w || h)){
    
    memset(g, false, sizeof(g));
    for(int i = 1; i <= h * 2 - 1; i++){
      if(i % 2 == 1){
	for(int j = 1; j <= w - 1; j++){
	  cin >> can;
	  if(can == 0){
	    g[i/2+1][j][i/2+1][j+1] = true;
	    g[i/2+1][j+1][i/2+1][j] = true;
	  }
	}
	
      }else{
	for(int j = 1; j <= w; j++){
	  cin >> can;
	  if(can == 0){
	    g[i/2][j][i/2+1][j] = true;
	    g[i/2+1][j][i/2][j] = true;
	  }
	}
      }
    }
  
    memset(memo, -1, sizeof(memo));
    memo[1][1] = 1;
    queue<P> que;
    que.push(P(1, 1));
    while(!que.empty()){
      P p = que.front();
      que.pop();
      int y = p.first;
      int x = p.second;
      for(int i = 0; i < 4; i++){
	int y2 = y + dy[i];
	int x2 = x + dx[i];
	if(g[y][x][y2][x2] && memo[y2][x2] == -1){
	 
	  memo[y2][x2] = memo[y][x] + 1;
	  que.push(P(y2, x2));
	}
      }
    }
    int res = memo[h][w];
    if(res == -1) cout << 0 << endl;
    else cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 3412
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
 
const int mx=100010;
const ll mod=1e9+7;

int main(){
  int a,b;
  cin >>a >>b;
  if(a<=b){
    cout << "unsafe" << endl;
  } else {
    cout << "safe" << endl;
  }
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); ++i)
#define pb push_back
#define all(v) v.begin(),v.end()
#define sort_1(v) sort(v.begin(),v.end())
#define sort_2(v) sort(v.begin(),v.end(),greater<ll>())
#define reverse(v) reverse(v.begin(),v.end())
typedef long long ll;
typedef long double la;
using namespace std;

int main(){
    string s;
    cin >> s;
    cout << s[0] << s[1] << s[2] << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
using namespace std;
typedef long long ll;
const double PI=acos(-1);
typedef pair<int,int>P;
const int mod =1e9+7;



int main()
{
    int n;
    ll h;
    
    cin>>n>>h;
    vector<ll>a(n);
    vector<ll>b(n);
    rep(i,n)cin>>a[i]>>b[i];
    sort(a.begin(),a.end());
    sort(b.begin(),b.end(),greater<ll>());
    ll ans=0;
    for(auto v:b)
    {
        if(v>=a[n-1])
        {
            h-=v;
            ans++;
        }
        if(h<=0)
        {
            cout<<ans;
            return 0;
        }
    }
    ans+=h%a[n-1]==0?h/a[n-1]:h/a[n-1]+1;
    cout<<ans;

}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <memory>

using namespace std;

struct Node {
  int key;
  Node* parent;
  Node* left;
  Node* right;
  
  Node(int key = -1) : key(key), parent(nullptr), left(nullptr), right(nullptr) {};
};

struct Tree {
  Node* root;  
  
  Tree() : root(nullptr) {};
};

static void insert(Tree& tree, int v) {
  Node* z = new Node(v);
  Node* x(tree.root);
  Node* y(nullptr);
  while (x != nullptr) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  
  z->parent = y;
  if (y == nullptr) {
    tree.root = z;
  } else if (z->key < y->key) {
    y->left = z;
  } else {
    y->right = z;
  }
}

static Node* find(Node* node, int v) {
  while (node != nullptr && node->key != v) {
    if (node->key > v) {
      node = node->left;
    } else {
      node = node->right;
    }
  }
  return node;
}

static Node* getSuccessor(Node* x) {
  if (x->right) {
    x = x->right;
    while (x->left) {
      x = x->left;
    }
    return x;
  }
  
  Node* y = x->parent;
  while (y && x == y->right) {
    x = y;
    y = y->parent;
  }
  return y;
}

static void deleteNode(Node*& root, int v) {
  Node* z = find(root, v);
  Node* y;
  if (!z->left || !z->right) {
    y = z;
  } else {
    y = getSuccessor(z);  
  }

  Node* x;
  if (y->left) {
    x = y->left;
  } else {
    x = y->right;
  }
  
  if (x) {
    x->parent = y->parent;
  }
  
  if (!y->parent) {
    root = x;    
  } else if (y == y->parent->left) {
    y->parent->left = x;
  } else {
    y->parent->right = x;
  }
  
  if (y != z) {
    z->key = y->key;  
  }
}

void preorderWalk(const Node* node) {
  if (!node) {
    return;
  }
  cout << " " << node->key;
  if (node->left != nullptr) {
    preorderWalk(node->left);
  }
  if (node->right != nullptr) {
    preorderWalk(node->right); 
  }
}

void inorderWalk(const Node* node) {
  if (!node) {
    return;
  }
  if (node->left != nullptr) {
    inorderWalk(node->left);
  }
  cout << " " << node->key;

  if (node->right != nullptr) {
    inorderWalk(node->right); 
  }
}

static Tree TREE;

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

  string command;
  int v;
  for (int i = 0; i < n; i++) {
    cin >> command;
    if (command[0] == 'i') {
      scanf("%d", &v);
      insert(TREE, v);
    } else if (command[0] == 'f') {
      scanf("%d", &v);
      Node* found = find(TREE.root, v);
      cout << (found ? "yes" : "no") << endl;
    } else if (command[0] == 'd') {
      scanf("%d", &v);
      deleteNode(TREE.root, v);
    } else {
      inorderWalk(TREE.root);
      cout << endl;
      preorderWalk(TREE.root);
      cout << endl;
    }
  }

  return 0;
}



Measured memory_bytes: 21960
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

using ll = long long;

void read();
template<typename First, typename... Rest> void read(First& first, Rest&... rest);
void write();
template<typename First, typename... Rest> void write(First first, Rest... rest);
template<typename T> void write_vec(vector<T>& v, char divider);

int main(){
    int N;
    string S;
    read(N, S);
    int ans = 1;
    for(int i = 0; i < N - 1; i++){
        if(S[i] != S[i + 1]) {
            ans++;
        }
    }
    write(ans);
    return 0;
}

//配列以外の入力を受け取る
void read(){

}
template<typename First, typename... Rest>
void read(First& first, Rest&... rest){
    cin >> first;
    read(rest...);
}
//
//配列以外を出力する
void write(){

}
template<typename First, typename... Rest>
void write(First first, Rest... rest){
    cout << first << " ";
    write(rest...);
}
//
//配列を区切って出力する
template<typename T>
void write_vec(vector<T>& v, char divider){
    for(size_t i = 0; i < v.size(); i++){
        cout << v[i] << divider;
    }
}
//

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

int main(void) {
  int n;
  string s;
  cin >> n >> s;
  rep(i, s.size()) {
    if (s[i] + n > 'Z') {
      s[i] = 'A' + (n - 1 - ('Z' - s[i]));
    } else {
      s[i] += n;
    }
  }
  cout << s << '\n';
  return 0;
}

Measured memory_bytes: 3592
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    string s; cin >> s;
    int N = s.size();
    vector< pair<char, int> > rle;
    for(int i=0; i<N; i++) {
        if(rle.empty() or rle.back().first != s[i]) rle.emplace_back(s[i], 1);
        else rle.back().second++;
    }

    if(rle.front().first == '>') rle.insert(rle.begin(), make_pair('<', 1));
    if(rle.back().first == '<') rle.insert(prev(rle.end()), make_pair('>', 1));

    ll ans = 0;
    for(size_t i=0; i<rle.size(); i+=2) {
        ll a = rle[i].second, b = rle[i+1].second;
        ll m = max(a, b);
        ans += m;
        ans += a * (a - 1) / 2;
        ans += b * (b - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3068
#include <stdio.h>
#include <math.h>

int	main(void)
{
  	int		L;
  	double	dL;
  	double	ans;
  	int		num;
  
  	num = scanf("%d", &L);
  	if (num != 1)
      	return (0);
  
  	dL = (double)L;
  
  	ans = dL / 3.0 * dL / 3.0 * dL / 3.0;
  	printf("%f", ans);
  	return (0);
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long>vll;
typedef pair<int,int> pi;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

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

/* 現在地 コスト 使った枚数 */
typedef tuple<int,int,int> tp;
typedef pair<ll,ll> P;

/* 町 使った割引券の数 */
ll dist[105][15];
vector<P> G[105];
const ll MAX=LLONG_MAX/10;

void init(){
  for(int i=0;i<105;i++){
    G[i].clear();
    for(int j=0;j<15;j++){
      dist[i][j]=MAX;
    }
  }
}

void solve(int c,int n,int m,int s,int d){
  init();
  int a,b,f;
  for(int i=0;i<m;i++){
    cin>>a>>b>>f;
    G[a].push_back(mp(b,f));
    G[b].push_back(mp(a,f));
  }

  /* 現在地 使った枚数 */
  priority_queue<tp,vector<tp>,greater<tp> > que;
  que.push(make_tuple(s,0,0));
  dist[s][0] = 0;
  while(que.size()){
    ll now,cost,num;
    tie(now,cost,num)=que.top();que.pop();
    if(dist[now][num]<cost)continue;
    for(auto x : G[now]){      
      /* 割引券を使わない */
      if(cost+x.second<dist[x.first][num]){
        dist[x.first][num] = cost+x.second;
        que.push(make_tuple(x.first,dist[x.first][num],num));
      }
      /* 割引券が残っていたら使う */
      if(num<c&&cost+x.second/2<dist[x.first][num+1]){
          dist[x.first][num+1] = cost+x.second/2;
          // cout<<now<<" "<<x.first<<" = "<< dist[x.first][num+1] << endl;
          que.push(make_tuple(x.first,dist[x.first][num+1],num+1));
        }
    }
  }

  ll ans=LLONG_MAX;
  for(int i=0;i<15;i++)
      ans=min(ans,dist[d][i]);
  ans=min(ans,dist[d][c]);
  
  cout<<ans<<endl;
}


int main(){
  int c,n,m,s,d;
  while(cin>>c>>n>>m>>s>>d,c|n|m|s|d){
    solve(c,n,m,s,d);
  }
}
	 



Measured memory_bytes: 3120
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	a = a - b;
	c = c - a;
	if (c < 0) {
		c = 0;
	}
	cout << c;
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("-Ofast")

#include <bits/stdc++.h>

using namespace std;

signed main(){
    int a,b;
    cin >> a >> b; 
    if (abs(b - a) & 1){ // bとaの差が奇数ならIMPOSSIBLE
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    cout << (a + b) / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
long long int mod = (long long int)1000000007;
using namespace std;

ll d[10000002];

void solve()
{
    ll i,j,k,n;
    std::cout.precision(10);
    int yes=0;
  cin>>n;
 
  for(i=1;i<=n;i++)
  {
      d[i]++;
    for(j=2*i;j<=n;j+=i)
    {
     	d[j]++; 
    }
  }
//   for(i=1;i<=4;i++)
//   {
//       cout<<d[i]<<" ";
//   }
  ll ans=0;
  for(i=1;i<=n;i++)
  {
    	ans+=i*d[i];
  }	
  cout<<ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    int i,j,k;
    int t;
    std::cout.precision(10);
    t=1;
    while(t--)
    {
        solve();
        cout<<"\n";
    }
}

Measured memory_bytes: 81772
#include <iostream>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<map>
#include<set>
#include<queue>
#include<deque>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < n;i++)
int main() {
	ld a, b, x, y;cin >> a >> b >> x >> y;
	cout << fixed << setprecision(10)<< a * b / 2  <<" ";
	if (x * 2 == a && y * 2 == b) {
		cout << 1 << endl;
	}
	else cout << 0 << endl;
}

Measured memory_bytes: 256
from sys import stdin


def iterate_tokens():
    for line in stdin:
        for word in line.split():
            yield word


def main():
    tokens = iterate_tokens()
    N = int(next(tokens))
    Q = int(next(tokens))
    S = next(tokens)
    L = [int()] * Q
    R = [int()] * Q
    for i in range(Q):
        L[i] = int(next(tokens)) - 1
        R[i] = int(next(tokens)) - 1
    AC = [int()] * N
    pre = None
    cnt = 0
    for i, c in enumerate(S):
        if c == "A":
            pre = "A"
        elif pre == "A" and c == "C":
            cnt += 1
            pre = None
        elif pre == "A":
            pre = None
        AC[i] = cnt
    for i in range(Q):
        print(AC[R[i]] - AC[L[i]])
    return


main()


Measured memory_bytes: 14188
n = gets.to_i
x__list = gets.split(" ").map(&:to_i)

result = Float::INFINITY
100.times do |i|
  sum = 0
  x__list.each do |x|
    sum += (x - i) ** 2
  end
  if sum < result then
    result = sum
  end
end

puts result

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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

//#define _USE_MATH_DEFINES
//#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>
#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef int long long i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1000000007ll;
const i64 smod = 998244353ll;
const i64 inf = 1000000007; // 10000000000000007ll;

const double eps = 1e-8;

const i64 MAXN = 400005;
const i64 MAXM = 20;


i64 n;

i64 a[MAXN];

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);


    string t = "hi";
    string s;
    cin >> s;

    while (1) {
        if (s.size() == 0) {
            cout << "Yes" << endl;
            return 0;
        }

        if (s.size() < t.size()) {
            cout << "No" << endl;
            return 0;
        }

        if (s.substr(0, 2) != t) {
            cout << "No" << endl;
            return 0;
        }

        s = s.substr(2);
    }


    return 0;
}

Measured memory_bytes: 256
import java.io.{BufferedReader, InputStream, InputStreamReader}
import java.util.StringTokenizer

import scala.collection.mutable
import scala.util.Sorting
import math.{abs, max, min}

object Main {
  def solve(): Unit = {
    val sc = new InputReader(System.in)
    val N = sc.nextInt()
    val A = sc.nextLong()
    val B = sc.nextLong()
    val C = A - B

    val h = Array.fill(N)(sc.nextLong())
    Sorting.quickSort(h)

    def extincts(k: Long): Boolean = {
      val ub = upperBound(h, k * B)
      val sum = ((ub until N) map { i =>
        val j = h(i) - B * k
        if (j <= 0)
          0
        else
          j / C + (if (j % C > 0) 1 else 0)
      }).sum
      sum <= k
    }

    def step(l: Long, h: Long): Long = {
      if (h - l == 1) h
      else {
        val mid = l + (h - l) / 2
        if (extincts(mid)) step(l, mid)
        else step(mid, h)
      }
    }

    val ans = step(-1, 1000000000)
    println(ans)
  }

  def main(args: Array[String]): Unit = {
    solve()
  }


  private def upperBound(a: Array[Long], x: Long): Int = {
    def step(l: Int, h: Int): Int = {
      if (h - l == 1) h
      else {
        val mid = (h + l) / 2
        if (a(mid) > x) step(l, mid)
        else step(mid, h)
      }
    }
    step(-1, a.length)
  }

  private class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = null

    def next: String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next.toInt
    def nextLong(): Long = next.toLong
    def nextChar(): Char = next.charAt(0)
  }

}


Measured memory_bytes: 113552
#include<bits/stdc++.h>
/* #define int long long */
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define repa(i, s, n) for(int i = s; i < (int)n; i++)
using namespace std;
using ll = long long;
typedef vector<int> vi;
typedef pair<int, int> P;
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main(){
    int n;
    cin >> n;
    vi p(n);
    rep(i, n) cin >> p[i], p[i]--;
    int ans = 0;

    for(int i = 0; i < n; i++){
        if(i == p[i]){
            ans++;
            i++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1e9+7,INF=mod*mod*3;//M_PI
#define rep(i,N) for(ll i=0; i<(N); i++)
#define rep1(i,N) for(ll i=1; i<(N); i++)
#define pb push_back

ll N;
ll fans=INF;
char C[200005];
ll cnt[200005];
ll ans[200005];

int main(){

cin.tie(0);
ios::sync_with_stdio(false);

cin>>N>>C;
rep(i,N){
	cnt[i+1]=cnt[i];
	if(C[i]=='R') cnt[i+1]++;
}
if(cnt[N]==N||cnt[N]==0){
	cout<<0<<endl; exit(0);
}
rep(i,N+1){
	ll Cwhite=i-cnt[i];
	ll Cred=cnt[N]-cnt[i];
	if(Cwhite<=Cred) ans[i]=Cred;
	else ans[i]=Cwhite;
}
rep(i,N+1) fans=min(fans,ans[i]);
cout<<fans<<endl;

}
	

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

#define int long long
#define pb push_back
#define mod 1000000007
#define endl '\n'
#define w(x) int x;cin>>x; while(x-->0)

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

void mysol()
{
    int n; cin >> n;
    int arr[n + 1][3];
    // memset(arr, 0, sizeof arr);
    for (int i = 0; i < 3; i++)
        arr[0][i] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 3; j++)
            cin >> arr[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 3; j++) {
            int t = INT_MIN;
            for (int k = 0; k < 3; k++)
            {
                if (j == k)
                    continue;
                else
                    t = max(t, arr[i - 1][k]);
            }
            arr[i][j] += t;
        }
    cout << max(arr[n][0], max( arr[n][1], arr[n][2]));
}

int32_t main()
{
    //fast();
    // w(t)
    {
        mysol();
    }
    return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
template <typename T> using vec = vector<T>;

int main()
{
    int n,m;
    cin >> n >> m;
    bool flag = true;
    vec<int> num(n,-1);
    int s,c;
    while(cin >> s >> c)
    {
        s--;
        if (num[s]!= -1 and num[s] != c)
        {
            flag = false;
            break;
        }
      	else if(s==0 and c==0 and n>=2)
        {
          	flag = false;
          	break;
        }
        else
        {
            num[s] = c;
        }
    }
    if (flag)
    {
        for (auto &&e : num)
        {
            e = max(0,e);
        }
        if(n!=1)
            num[0] = max(num[0],1);
        auto sum = accumulate(num.begin(),num.end(),0,[](auto a,auto b)
        {
            return a*10+b;
        });
        cout << sum << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    
    
}

Measured memory_bytes: 256
import itertools
N, K = map(int, input().split())
d = [0]*K
a = [0]*K

for i in range(K):
    d[i] = int(input())
    a[i] = list(map(int, input().split()))

menber = list(range(1, N+1))
have_list = list(set(itertools.chain.from_iterable(a)))

res = len(menber) - len(have_list)
print(res)

Measured memory_bytes: 9296
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

int main() {
    int n;
    cin >> n;
    vector<ll> v(n);
    rep(i, n) cin >> v[i];

    int mi = 0;
    ll ans = 0;
    rep(i, n) {
        ll t = v[i];
        if (i == 0) {
            mi = 1;
            ans += t - 1;
        } else if (t <= mi) continue;
        else if (t == mi + 1) {
            mi = mi + 1;
        } else {
            ans += ((t - 1) / (mi + 1));
        }
    }
    cout << ans << endl;

}


Measured memory_bytes: 4032
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> IP;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)

int main() {
	int N;
	cin >> N;
	vector<lint>A(N);
	rep(i, N) {
		cin >> A[i];
	}
	int M;
	cin >> M;
	vector<lint>B(M);
	rep(i, M) {
		cin >> B[i];
	}
	set<lint>SA;
	rep(i, N) {
		SA.insert(A[i]);
	}
	rep(i, M) {
		if (SA.count(B[i])) {

		}
		else {
			cout << 0 << endl;
			return 0;
		}
	}
	cout << 1 << endl;
}




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

#define rep(l, r) for (int i = (l); i < (r); i++)

typedef long long ll;
 
using namespace std;
 
int main() {
    int n, m;
    cin >> n >> m;

    int p, all_penalties = 0, collects = 0;
    string s;
    bool ac[n];
    int penalties[n];
    memset(ac, false, sizeof(ac));
    memset(penalties, 0, sizeof(ac));
    rep(0, m) {
        cin >> p >> s;

        if (s == "WA") {
            if (!ac[p-1]) penalties[p-1]++;
        } else if (s == "AC") {
            if (!ac[p-1]) {
                all_penalties += penalties[p-1];
                collects++;
                ac[p-1] = true;
            }
        }
    }

    printf("%d %d\n", collects, all_penalties);

    return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
  #include "_DEBUG.hpp"
#endif
#define int long long
const int INF = 1LL << 60;

#define double long double //大正義!!!

signed main(){

  int a, b, c; cin >> a >> b >> c;

  int d = c - a - b;
  if(d <= 0){
    cout << "No" << endl;
    return 0;
  }
  if(4*a*b < d*d){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

  return 0;
}

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

template <class T>
class CHT {
  int size;
  vector<T> xs;
  vector<pair<T,T>> vec;
  unordered_map<T, int> mp;
  
  void putSub(T a, T b, int l, int r) {
    // cerr << "putSub " << l << " " << r << endl;
    int m = (l + r) / 2;
    T a0 = vec.at(m).first;
    T b0 = vec.at(m).second;
    T x = xs.at(m);
    if (isnan(a0)) {
      vec.at(m) = {a, b};
      return;
    }
    if (!(a0 * x + b0 >= a * x + b)) {
      vec.at(m) = {a, b};
      swap(a0, a);
      swap(b0, b);
    }
    if (!(a0 * xs.at(l) + b0 >= a * xs.at(l) + b)) {
      putSub(a, b, l, m-1);
    }else if (!(a0 * xs.at(r) + b0 >= a * xs.at(r) + b)) {
      putSub(a, b, m+1, r);
    }
  }

  T getSub(T ans, T x, int i, int l, int r) {
    // cerr << "getSub " << l << " " << r << endl;
    int m = (l + r) / 2;
    T a = vec.at(m).first;
    T b = vec.at(m).second;
    if (isnan(a)) return ans; 
    if (l == 0 && r == size-1) {
      ans = a * x + b;
    }else {
      ans = max(ans, a*x + b);
    }
    return (i == m) ? ans :
           (i <  m) ? getSub(ans, x, i, l, m-1) :
                      getSub(ans, x, i, m+1, r) ;
  }

public:
  CHT(const vector<T>& _xs)
        : size(_xs.size()), xs(_xs), vec(size, {nan(""), 0}) {
    sort(xs.begin(), xs.end());
    for (int i = 0; i < size; i++) {
      mp[xs.at(i)] = i;
    }
  }

  void put(T a, T b) {
    putSub(a, b, 0, size-1);
  }

  T get(T x) {
    int i = mp.at(x);
    return getSub(0, x, i, 0, size-1);
  }

};


int main(int argc, char *argv[]) {
  // C-style stdio functions should not be used.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N, C; cin >> N >> C;
  vector<ll> H(N);
  for (int i = 0; i < N; i++) cin >> H.at(i);
  
  /*
    (Hj-Hi)^2 + C
    dp[0] = 0
    dp[i] = min { dp[j] + (Hi - Hj)^2 + C | j < i }
          = Hi^2 + C + min { -2 Hi Hj + Hj^2 + dp[j] | j < i }
   */
  
  vector<ll> dp(N);
  dp.at(0) = 0;
  CHT<ll> cht(H);
  for (int i = 0; i < N-1; i++) {
    cht.put(-(-2 * H.at(i)), -(H.at(i) * H.at(i) + dp.at(i)));
    dp.at(i+1) = -cht.get(H.at(i+1)) + H.at(i+1) * H.at(i+1) + C;
  }
  cout << dp.at(N-1) << endl;

  return 0;
}



Measured memory_bytes: 16328
// In the name of Allah
// #Isart

#include<bits/stdc++.h>

#define pii pair<int, int>
#define pb push_back
#define F first
#define S second
#define ll long long
#define ld long double

using namespace std;

const int MAXN = 5e3 + 10, MAXM = 200 + 10;
ll ans[MAXN][MAXN], b[MAXN][MAXM], a[MAXN], ps[MAXN];
int l[MAXN], r[MAXN];
vector<pair<int, int> > v;
vector<int> c;

inline void add(int x, int y, int z, int w, ll val){
	y ++; w ++;
	ans[x][z] += val;
	ans[y][z] -= val;
	ans[x][w] -= val;
	ans[y][w] += val;
	return;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int n, m; cin >> n >> m;

	for(int i = 0; i < n - 1; i ++) cin >> a[i], ps[i + 1] = ps[i] + a[i];

	for(int i = 0; i < n; i ++)
		for(int j = 0; j < m; j ++)
			cin >> b[i][j];

	for(int i = 0; i < m; i ++){
		v.clear();
		for(int j = 0; j < n; j ++)
			v.pb({b[j][i], j});
		fill(l, l + n, -1);
		fill(r, r + n, n);
		c.clear();
		for(int j = 0; j < n; j ++){
			while(c.size() and v[c.back()].F < v[j].F){
				r[c.back()] = j;
				c.pop_back();
			}
			c.pb(j);
		}
		c.clear();
		for(int j = n - 1; j > -1; j --){
			while(c.size() and v[c.back()].F <= v[j].F){
				l[c.back()] = j;
				c.pop_back();
			}
			c.pb(j);
		}

		for(int j = 0; j < n; j ++){
			add(l[j] + 1, j, j, r[j] - 1, v[j].F);
		}
	}

	for(int i = 0; i < n; i ++){
		for(int j = 0; j < n; j ++){
			if(i) ans[i][j] += ans[i - 1][j];
			if(j) ans[i][j] += ans[i][j - 1];
			if(i and j) ans[i][j] -= ans[i - 1][j - 1];
		}
	}

	ll fans = 0;
	for(int i = 0; i < n; i ++){
		for(int j = i; j < n; j ++){
			ans[i][j] -= ps[j] - ps[i];
			fans = max(fans, ans[i][j]);

		}
	}

	cout << fans << endl;

	return 0;	
}

Measured memory_bytes: 204416
# coding: utf-8
from queue import PriorityQueue

(n,m) = map(int, input().rstrip().split(" "))

sinamono = [int(i) * -1 for i in input().rstrip().split(" ")]

q = PriorityQueue()
for i in sinamono:
    q.put(i)

for i in range(m):
    item = q.get()
    q.put(int(item/2))

ans = 0
while not q.empty():
    ans += q.get()
print(ans * -1)


Measured memory_bytes: 15292
#include <iostream>

int main() {
  int a, b, c, d;
  
  std::cin >> a >> b >> c >> d;
  
  if ((a + b) > (c + d)) {
    std::cout << "Left\n";
  } else if((a + b) < (c + d)) {
    std::cout << "Right\n";
  } else {
    std::cout << "Balanced\n";
  }
  
  return 0;
}

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


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

# In[15]:


N = int(input())
v = list(map(int, input().split()))


# In[16]:


mylist = sorted(v)
while True:
    tmp = (mylist[0] + mylist[1]) / 2
    del mylist[:2]
    mylist.insert(0, tmp)
    if len(mylist) == 1:
        print(mylist[0])
        break


# In[ ]:






Measured memory_bytes: 2940
#include<iostream>

using namespace std;

int main()
{
  int d;
  cin>>d;
  for(;d--;)
    {
      int x,y,w,h;
      cin>>x>>y>>w>>h;
      int n;
      cin>>n;
      int ans=0;
      for(;n--;)
	{
	  int xx,yy;
	  cin>>xx>>yy;
	  if(xx>=x &&
	     yy>=y &&
	     xx<=x+w &&
	     yy<=y+h)
	    ans++;
	}
      cout<<ans<<endl;
    }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define dd(x) cout<<#x<<" = "<<x<<" "
#define de(x) cout<<#x<<" = "<<x<<"\n"
#define sz(x) int(x.size())
#define All(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef priority_queue<int> BQ;
typedef priority_queue<int,vector<int>,greater<int> > SQ;
const int maxn=3e5+10,mod=1e9+7,INF=0x3f3f3f3f;
char s[maxn][5];
int a[5];
int main()
{
	int n;
	cin>>n>>a[0]>>a[1]>>a[2];
	for (int i=1;i<=n;++i)
		scanf("%s",s[i]);
	vector<int> ans;
	for (int i=1;i<=n;++i){
		int x=s[i][0]-'A',y=s[i][1]-'A';
		if (a[x]==a[y]&&a[x]==1){
			if (i+1<=n){
				int nx=s[i+1][0]-'A',ny=s[i+1][1]-'A';
				if (!(nx==x&&ny==y)){
					if (nx==x||ny==x)
						a[x]++,a[y]--,ans.pb(x);
					else
						a[x]--,a[y]++,ans.pb(y);
				}
				else
					a[x]++,a[y]--,ans.pb(x);
			}
			else
				a[x]++,a[y]--,ans.pb(x);
		}
		else{
			if (a[x]>a[y])
				a[x]--,a[y]++,ans.pb(y);
			else
				a[x]++,a[y]--,ans.pb(x);
		}
		if (a[x]<0||a[y]<0){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes\n";
	for (auto i:ans)
		printf("%c\n",i+'A');
	return 0;
}


Measured memory_bytes: 4476
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
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;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"YES"<<"\n"
#define no cout<<"NO"<<"\n"

typedef ll Def;
Def d[1010][1010];
Def dame[1010][1010];
class DIJ{
	public:
	struct edge{
		Def to,cost;
	};
	Def n,m,a,b;
	vs in;
//	vector<vector<Def> >d;//distance
	DIJ(Def H,Def W,Def A,Def B,vs tmp){
		n=H,m=W;a=A,b=B;
		in=tmp;
	}
	void dij(){
		
		rep(i,1010)rep(j,1010)d[i][j]=inf;
		priority_queue<tp>q;
		rep(i,n)rep(j,m)if(in[i][j]=='s')d[i][j]=0,dame[i][j]=0,
										q.push(tp(0,i,j));

		rep(i,n)rep(j,m)if(in[i][j]=='*'){
			rep(I,3)rep(J,3){
				int x=i+I-1,y=j+J-1;
				if(x<0||y<0||x>=n||y>=m)continue;
				dame[x][y]=1;
			}
		}
		while(!q.empty()){
			Def cost,x,y;
			tie(cost,x,y)=q.top();
			cost*=-1;
			q.pop();
			// cout<<cost<<" "<<x<<" "<<y<<endl;
			if(cost>d[x][y])continue;
			rep(i,3)rep(j,3){
				int nx=x+i-1,ny=y+j-1;
				if(nx<0||ny<0||nx>=n||ny>=m)continue;
				Def ncost=cost;//??????
				if(in[nx][ny]=='#'){
					if(dame[x][y])continue;
					if(abs(i-1)+abs(j-1)==2)ncost+=a+a+b;
					else ncost+=a+b;
				}else{
					if(abs(i-1)+abs(j-1)==2)continue;
					ncost+=a;
				}
				if(ncost<d[nx][ny]){
					d[nx][ny]=ncost;
					q.push(tp(-ncost,nx,ny));
				}
			}
		}
		int out;
		rep(i,n)rep(j,m)if(in[i][j]=='g')out=d[i][j];
		if(out==inf)cout<<"INF"<<endl;
		else cout<<out<<endl;
	}
};

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,m,a,b;
	cin>>n>>m>>a>>b;
	vs in(n);
	rep(i,n)cin>>in[i];
	DIJ dij(n,m,a,b,in);
	dij.dij();
}


Measured memory_bytes: 20808
N, K = map(int, input().split())
prob = 0

for i in range(1, N+1):
    x = 0
    num = i * 2 ** x
    
    while (K > num):
        x += 1
        num = i * 2 ** x        
        
    prob += 1 / N * (1 / 2) ** x

print(prob)

Measured memory_bytes: 2940
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;
// const int imax = 100000;

int main(){
	int a,b;
	cin >> a >> b;
	if(b%a==0) printf("%d\n",a+b);
	else printf("%d",b-a);
	return 0;
}




Measured memory_bytes: 3732
/*ex3_2
    takafumi_ueki*/
#include <stdio.h>
int main(void){
    int A;
    scanf("%d",&A);
    //Aを１０割った余り、つまり１の位が何かによって条件分岐
    //”||”は、またはという意味
        if((A%10 == 2)||(A%10 == 4)||(A%10 == 5)||(A%10 == 7)||(A%10 == 9)){
        printf("hon\n");
    }
    if((A%10 == 0)||(A%10 == 1)||(A%10 == 6)||(A%10 == 8)){
        printf("pon\n");
    }
    if(A%10 == 3){
        printf("bon\n");
    }
    return 0;
}


Measured memory_bytes: 1660
#![allow(non_snake_case)]
use proconio::{input, fastout};
// use proconio::marker::{Chars, Bytes, Usize1};
// use std::cmp::*;

#[fastout]
fn main() {
    input!{
        mut x:i64, k:i64, d:i64
    };
    if x < 0 {
        x = -x;
    }
    let mut c;
    if x / d > k {
        c = x - d * k;
    } else {
        c = x % d;
        let v = k - x / d;
        if v & 1 > 0 {c = d - c}
    }
    println!("{}", c);
}


Measured memory_bytes: 2200
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main(){
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  vector<int> B(M);
  for (int i = 0; i < M; i++){
    cin >> B[i];
  }
  sort(A.rbegin(), A.rend());
  sort(B.rbegin(), B.rend());
  A.push_back(0);
  B.push_back(0);
  bool ok = true;
  for (int i = 0; i < N - 1; i++){
    if (A[i] == A[i + 1]){
      ok = false;
    }
  }
  for (int i = 0; i < M - 1; i++){
    if (B[i] == B[i + 1]){
      ok = false;
    }
  }
  if (!ok){
    cout << 0 << endl;
  } else {
    int R = 0;
    int C = 0;
    long long ans = 1;
    for (int i = N * M; i >= 1; i--){
      if (A[R] == i){
        R++;
        if (B[C] == i){
          C++;
        } else {
          ans *= C;
        }
      } else if (B[C] == i){
        C++;
        ans *= R;
      } else {
        ans *= R * C - (N * M - i);
      }
      ans %= MOD;
    }
   cout << ans << endl;
  }
}

Measured memory_bytes: 3624
#include<iostream>
using namespace std;
int main(){
  
  long long int n;
  cin>>n;
  long long int i=1;
  long long int k=7;
  int temp=0;
  while(i<=n)
  {
    if(k%n==0)
    {
      cout<<i<<endl;
      temp=1;
      break;
      
    }
    k=(k%n)*10+7;
    
    i++; 
  }
  if(temp==0)
  cout<<"-1"<<endl;
  
  
  
  
  
  
  
  return 0;
  
  
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <stdio.h>
#include <math.h>
#include <cstdlib>
#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
using ll = long long;
const int INF = 1e9 + 5;

void print_vector(vector<vector<ll> >v){
    for(ll i=0;i<v.size();i++){
        for(ll j=0;j< v[i].size();j++){
            cout<<v[i][j]<<" ";
        }cout<<"\n";
    }
}
ll gcd(ll a, ll b)
{
    if (a == 0)
       return b;
    if (b == 0)
       return a;
    if (a == b)
        return a;
    if (a > b)
        return gcd(a-b, b);
    return gcd(a, b-a);
}

int main(){
    ll k,sum=0;
    cin>>k;
    for(ll i=1;i<=k;i++){
        for(ll j=1;j<=k;j++){
            for(ll m=1;m<=k;m++){
                sum=sum+gcd(gcd(i,j),m);
            }
        }
    }
    cout<<sum;
    return 0;
}



Measured memory_bytes: 3592
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>
#include <climits>

using namespace std;

int main() {
    int n,m;
    cin >> n >> m;
    vector<int> ary(m+1, 0);
    for(int i=0; i<n; i++) {
        int k;
        cin >> k;
        for(int j=0; j<k; j++) {
            int a;
            cin >> a;
            ary[a]++;
        }
    }
    int v=0;
    for(int i=1; i<=m; i++) {
        if(ary[i] == n) {
            v++;
        }
    }
    cout << v << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>

#define NUM 100

static int *s;
static int N;

void STACK(int maxN);
void push(int x);
int pop(void);

int main(void){
	char x;
	int a,b;
	int e = 0;
	int i = 0, p = 0;
	
	STACK(NUM);
	
	while((x = getchar()) != EOF){
		if(isdigit(x)){
			i = i * 10 + (x - '0');			
			p = 1;
		}
		else{
		switch(x){		//switch?????§??´???????????????
		case '+':		//??????????????\??????????????¨???
			a = pop();	//????????????????????°?????????????????????,??????????????????????????????????????\
			b = pop();
			push(a + b);
			break;
			
		case '-':
			b = pop();
			a = pop();
			push(a - b);
			break;
			
		case '*':
			a = pop();
			b = pop();
			push(a * b);
			break;
			
		case '\n':		//Enter??§??????
			e = -1;
			break;
			
		
		case ' ':
			if(p != 0) {
				push(i);
				i = 0;
				p = 0;
			}
			break;
			
		default:
			break;
			
		}
		if (e == -1)break;
		}
	}
	printf("%d\n",pop());
	
	return 0;
}
	
	void STACK(int maxN){		//?????????????????????????????¢??°
		s = malloc(maxN * sizeof(int));
		N = 0;
	}
	
	void push(int x){		//push??¨??¢??°
		s[N++] = x;
	}
	
	int pop(void){		//pop??¨??¢??°
		if(N <= 0) {
			printf("stack pop error\n");
			return 0;
		}
		return s[--N];
	}

Measured memory_bytes: 1808
#include<bits/stdc++.h>
using namespace std;
int n;
 long long sm[200000];
 long long v[200000];

int f2(){
	 long long df=INFINITY;
	for(int i=0;i<n-1;i++){
		if(sm[n-1]-sm[i]==sm[i])return 0;
		 long long k=sm[n-1]-sm[i];
		df=min(df,abs(k-sm[i]));
	}
	return df;	
}

int main(){
ios_base::sync_with_stdio(0);
cin>>n;
cin>>v[0];
sm[0]=v[0];
for(int i=1;i<n;i++){
	cin>>v[i];
	sm[i]=sm[i-1]+v[i];
}
//for(auto i:sm)cout<<i<<' ';
//if(n==2)cout<<v[1]-v[0]<<'\n';
//cout<<sm[n-1]<<endl;
cout<<f2()<<'\n';
}



Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define MOD int(1e9+7)

int main()
{
    int n;cin>>n;
    string s;cin>>s;
    bool ok=true;;
    if(n%2!=0)ok=false;
    else
    {
        int i;
        for(i=0;i<n/2;i++)
        {
            if(s.at(i)!=s.at(i+n/2))ok=false;
        }
    }
    if(ok)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  int fiveTen,hund,fiveHund;
  int money;
  int i,j,k;
  int count = 0;
  
  if(scanf("%d\n",&fiveHund));
  if(scanf("%d\n",&hund));
  if(scanf("%d\n",&fiveTen));
  if(scanf("%d\n",&money));
  
  
  for(i=0;i<=fiveHund;i++){
    for(j=0;j<=hund;j++){
      for(k=0;k<=fiveTen;k++){
        if(500*i + 100*j + 50*k == money){
          count += 1; 
        } 
      }
    }  
  }     
    
  printf("%d",count);
  
  return 0;
}

Measured memory_bytes: 128