akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define FAST {ios_base::sync_with_stdio(false);cin.tie(NULL);}
#define f(i, a, b) for(ll i=a; i<b; i++)
#define fr(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pll pair<ll,ll>
#define LB lower_bound
#define UB upper_bound
#define endl "\n"
using namespace std;

int main()
{
    FAST
    ll x,k,d;cin>>x>>k>>d;
    ll dis = abs(x);
    ll stps = dis/d;
    if(stps>=k) cout<<(x>0?x-k*d:-k*d-x)<<endl;
    else
    {
        k-=stps;
        ll curd = dis%d;
        if(k&1LL) cout<<d-curd<<endl;
        else cout<<curd<<endl;
    }
    
}


Measured memory_bytes: 3656
<?php

fscanf(STDIN, '%s', $S);

$charArray = [];
foreach (str_split($S) as $val) {
    if ($val === '0') {
        $charArray[] = false;
    } else {
        $charArray[] = true;
    }
}

$count = 0;
$checkedChar = [];
for ($i = 0; $i < count($charArray); $i++) {
    if ($i === 0) {
        $checkedChar[] = $charArray[$i];
    } else {
        if ($charArray[$i] === $checkedChar[$i - 1]) {
            $count++;
            $checkedChar[] = !$charArray[$i];
        } else {
            $checkedChar[] = $charArray[$i];
        }
    }
}

echo $count . PHP_EOL;

Measured memory_bytes: 15992
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<string>
#include<bits/stdc++.h>
#include<vector>
using namespace std;
using ll = long long;
using lli = long long int;
ll MM = 1000000000;
ll mod = MM + 7;
#define INF (ll)1e18
#define pi acos(-1.0)
int main(){
    string s; cin >> s;
    ll n = s.size();
    vector<ll> a;
    ll cnt = 0;
    for(ll i = 0; i < n; i++){
        if(s[i] == 'B') a.push_back(i+1);
    }
    reverse(a.begin(), a.end());
    for(ll i = 0; i < a.size(); i++){
        cnt += n - a[i];
        n--;
    }
    cout << cnt << endl;
}

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

int main() {
  string S;
  cin >> S;
  if (S.at(2) == S.at(3) && S.at(4) == S.at(5)){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

#define FOR(i,a,b)    for (int i=(a)  ;i<(b) ;i++)
#define RFOR(i,a,b)   for (int i=(b)-1;i>=(a);i--)
#define REP(i,n)      for (int i=0    ;i<(n) ;i++)
#define RREP(i,n)     for (int i=(n)-1;i>=0  ;i--)
#define EACH(i,a,b)   for (int i=(a)  ;i<=(b);i++)
#define REACH(i,a,b)  for (int i=(b)  ;i>=(a);i--)
#define ALL(a)        (a).begin(),  (a).end()
#define RALL(a)       (a).rbegin(), (a).rend()
#define YES()         printf("YES\n")
#define NO()          printf("NO\n")
#define Yes()         printf("Yes\n")
#define No()          printf("No\n")
#define in(a,x,b)     ((a) <= (x) && (x) < (b))

const int MOD = 1e9 + 7;
const int INF = 1 << 29;
const double EPS = 1e-10;

using ll = long long;
using P = pair<int,int>;
template<class T = int> using V = vector<T>;

template<class T> bool inline chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool inline chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T = int> T inline input() { T x; cin >> x; return (x); }
template<class T> void inline print(T& x) { cout << x << '\n'; }
#define debug(x) cerr << #x << ": " << x << endl;

const int dxs[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
const int dys[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

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

  int N,M;
  cin >> N >> M;
  int A[N];
  REP(i,N) cin >> A[i];

  priority_queue<double> pq;
  REP(i,N) pq.push(A[i]);

  REP(i,M) {
    double x = pq.top() / 2;
    pq.pop();
    pq.push(x);
  }

  ll ans = 0;
  REP(i,N) {
    ans += (ll)(pq.top() + EPS);
    pq.pop();
  }

  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 4636
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
int main() {
    int N, M;
    cin >> N;
    int T[110];
    int t[110];
    for(int i = 1; i <= N; i++) cin >> T[i];
    cin >> M;
    int P[110];
    int X[110];
    for(int i = 1; i <= M; i++) cin >> P[i] >> X[i];
    int k = 1;
    while(k <= M){
        int sum = 0;
        for(int i = 1; i <= N; i++) t[i] = T[i];
        t[P[k]] = X[k];
        for(int j = 1; j <= N; j++) sum += t[j];
        cout << sum << endl;
        k++;
    }
    return 0;
}

Measured memory_bytes: 3684
MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))

F = [0 for _ in range(S + 1)]
res = 0

for i in range(N):
    F[0] += 1
    for j in range(S + 1)[::-1]:
        if j - A[i] >= 0:
            F[j] += F[j - A[i]]
    res += F[S]
    res %= MOD

print(res)

Measured memory_bytes: 67292
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
long long gcd(long long a, long long b){
   if (a % b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a % b));
   }
}
long long lcm(long long a, long long b){
   return (a / gcd(a, b))* b;
}
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------

void solve(){
}
int main(){
    long long n;
    cin >> n;
    vector<pair<long long, long long> >data(n);
    vector<pair<long long, long long> >wide(n);
    vector<pair<long long, long long> >wide2(n);
    for(int i = 0; i < n; i++){
        cin >> data.at(i).first >> data.at(i).second;
    }
    for(int i = 0; i < n; i++){
        wide.at(i).first = data.at(i).first + data.at(i).second;//より正よりのところ
        wide.at(i).second = data.at(i).first - data.at(i).second;//より負よりのところ
        wide2.at(i).first = wide.at(i).second;//より負よりのところ
        wide2.at(i).second = wide.at(i).first;//より正よりのところ
    }
    sort(wide.begin(), wide.end());//正側のアームがより負に近いところから並ぶ
    sort(wide2.begin(), wide2.end());//負側のアームがより負に近いところから並ぶ
    reverse(wide2.begin(), wide2.end());//負がわのアームがより正に近いところから並ぶ
    long long tmp = 0 - mod;
    long long ans1 = 0, ans2 = 0;
    for(int i = 0; i < n; i++){
        if(tmp <= wide.at(i).second){
            ans1++;
            tmp = wide.at(i).first;
            dump(tmp);
        }
    }
    tmp = mod;
    for(int i = 0; i < n; i++){
        if(tmp >= wide2.at(i).second){
            ans2++;
            tmp = wide2.at(i).first;
            dump(tmp);
        }
    }
    
    long long ans;
    dump(ans1);
    dump(ans2);
    ans = max(ans1, ans2);
    cout << ans << endl;
    solve();
    return 0;
}



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

#define int long long
const int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int dat[8][8];
  for ( int i = 0; i < 8; i++ ) {
    string s;
    cin >> s;
    for ( int j = 0; j < 8; j++ ) {
      if ( s[j] == 'o' ) dat[i][j] = 0;
      if ( s[j] == 'x' ) dat[i][j] = 1;
      if ( s[j] == '.' ) dat[i][j] = 2;
    }
  }

  int t = 0;
  int con = 0;  
  bool flag = true;
  while ( con < 2 ) {
    flag = false;
    int ma = 0;
    int y, x;    
    for ( int i = 0; i < 8; i++ ) {
      for ( int j = 0; j < 8; j++ ) {
	if ( dat[i][j] != 2 ) continue;
	int sum = 0;
	for ( int d = 0; d < 8; d++ ) {
	  int ny = i+dy[d], nx = j+dx[d];
	  if ( ny < 0 || nx < 0 || ny >= 8 || nx >= 8 ) continue;
	  if ( dat[ny][nx] != !t ) continue;
	  int cnt = 1;
	  while ( 1 ) {	    
	    ny += dy[d]; nx += dx[d];
	    if ( ny < 0 || nx < 0 || ny >= 8 || nx >= 8 ) break;
	    if ( dat[ny][nx] == t ) {
	      sum += cnt;
	      break;
	    } else if ( dat[ny][nx] == 2 ) {
	      break;
	    }
	    cnt++;	    
	  }
	}
	if ( sum ) flag = true;
	if ( !t && sum > ma ) {
	  ma = sum;
	  y = i;
	  x = j;	  
	}
	if ( t && sum >= ma ) {
	  ma = sum;
	  y = i;
	  x = j;	  
	}
      }
    }

    if ( !flag ) {
      con++;
      t = !t;
      continue;      
    }
    con = 0;    
    dat[y][x] = t;    
    for ( int d = 0; d < 8; d++ ) {
      int ny = y+dy[d], nx = x+dx[d];
      if ( ny < 0 || nx < 0 || ny >= 8 || nx >= 8 ) continue;
      if ( dat[ny][nx] != !t ) continue;
      bool flag2 = false;
      while ( 1 ) {	    
	ny += dy[d]; nx += dx[d];
	if ( ny < 0 || nx < 0 || ny >= 8 || nx >= 8 ) break;
	if ( dat[ny][nx] == t ) {
	  flag2 = true;
	  break;
	} else if ( dat[ny][nx] == 2 ) {
	  break;
	}	    
      }
      if ( !flag2 ) continue;
      ny = y+dy[d]; nx = x+dx[d];      
      if ( ny < 0 || nx < 0 || ny >= 8 || nx >= 8 ) continue;
      dat[ny][nx] = t;      
      while ( 1 ) {	    
	ny += dy[d]; nx += dx[d];
	if ( ny < 0 || nx < 0 || ny >= 8 || nx >= 8 ) break;
	if ( dat[ny][nx] == t ) {
	  break;
	} else if ( dat[ny][nx] == 2 ) {
	  break;
	}
	dat[ny][nx] = t;	
      }
    }
    t = !t;
  }

  for ( int i = 0; i < 8; i++ ) {
    for ( int j = 0; j < 8; j++ ) {
      if ( dat[i][j] == 0 ) cout << 'o';
      if ( dat[i][j] == 1 ) cout << 'x';
      if ( dat[i][j] == 2 ) cout << '.';
    }
    cout << endl;
  }
  
  return 0;
}



Measured memory_bytes: 3240
#include <stdio.h>

int a, b;

int digits(int n)
{
  if (n < 10) return 1;
  return digits(n/10) + 1;
}

int main(void)
{
  while(scanf("%d %d",&a,&b) == 2)
    printf("%d\n",digits(a + b));
  return 0;
}

Measured memory_bytes: 2724
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
int f(int n)
{
    if (n % 2 == 0)
    {
        return n / 2;
    }
    else
    {
        return 3 * n + 1;
    }
}

void _main()
{
    int s;
    cin >> s;
    set<int> ss;
    ss.insert(s);
    int a = s;
    int i = 0;
    while (true)
    {
        ++i;
        a = f(a);
        if (ss.find(a) != ss.end())
        {
            cout << i + 1 << endl;
            return;
        }
        ss.insert(a);
    }
}


Measured memory_bytes: 256
#include <stdio.h>

#define WIDTH 8
#define HEIGHT 8

char field[ WIDTH + 3 ][ HEIGHT + 2 ] = {};

int main( void ) {
	char type;
	int x, y;

	for ( ; ungetc( getchar(), stdin ) != EOF; printf( "%c\n", type ) ) {
		for ( y = 0; y < HEIGHT; y++ )
			for ( x = 1; x <= WIDTH; x++ )
				scanf( "%c ", field[ x ] + y );

		for ( y = 0; y < HEIGHT; y++ )
			for ( x = 1; x <= WIDTH; x++ )
				if ( field[ x ][ y ] == '1' ) {
					if ( field[ x + 2 ][ y ] == '1' )
						type = 'C';
					else if ( field[ x + 2 ][ y + 1 ] == '1' )
						type = 'E';
					else if ( field[ x + 1 ][ y + 2 ] == '1' )
						type = 'F';
					else if ( field[ x ][ y + 2 ] == '1' )
						type = 'B';
					else if ( field[ x - 1 ][ y + 2 ] == '1' )
						type = 'D';
					else if ( field[ x - 1 ][ y + 1 ] == '1' )
						type = 'G';
					else
						type = 'A';

					goto contin;
				}

		contin :;
	}

	return 0;
}

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

int main(){
    int n,k;
    cin >> n >> k;
    double ans = 0;
    for(int i=1;i<=n;i++){
        double cnt = 0,sum = i;
        while(sum < k){
            sum *= 2;
            cnt++;
        }
        ans += 1.0/n*(pow(1.0/2,cnt));
    }
    printf("%.16lf\n",ans);
    
}


Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
using namespace std;

int main(){
    string s,t;
    cin >> s >> t;
    sort(s.begin(),s.end());
    sort(t.begin(),t.end(),greater<int>());
    if(s<t){
        cout <<"Yes";
    }else{
        cout << "No";
    }
}

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

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl
#define lint long long
#define yes "Yes"
#define no "No"

typedef pair<int, int> P;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k; cin>>n>>k;
    if((n+1)/2>=k) print("YES");
    else print("NO");
    return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7

res = 0
for dig in range(61):
    one = 0
    for i in a:
        if i & (1<<dig) != 0:
            one += 1
    res = (res + one*(n-one)*(1<<dig))%MOD
print(res)

Measured memory_bytes: 123000
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;

int main() {
    string S, T;
    cin >> S >> T;
    bool fl = false;
    if(S.length() < T.length())
        S = "UNRESTORABLE";
    else {
        for(int i = S.length() - 1; i >= 0; --i) {
            if(fl) {
                if(S[i] == '?')
                    S[i] = 'a';
                continue;
            } else if(i < T.length() - 1 && !fl) {
                S = "UNRESTORABLE";
                continue;
            }
            bool match = true;
            for(int j = 0; j < T.length(); ++j) {
                if(S[i - j] != '?' && S[i - j] != T[T.length() - 1 - j])
                    match = false;
            }
            if(match) {
                for(int j = T.length() - 1; j >= 0; --j)
                    S[i - j] = T[T.length() - 1 - j];
                fl = true;
            } else if(S[i] == '?')
                S[i] = 'a';
        }
    }
    cout << S << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

const int INF = 1001001001;

void dfs(vector<vector<int>> &gr, vector<bool> &f, int now){
  f.at(now) = true;
  for(auto i : gr.at(now)){
    if(f.at(i) == true) continue;
    dfs(gr, f, i);
  }
}

bool update(vector<tuple<int, int, int>> &vt, vector<int> &d, vector<bool> &ff){
  bool ret = false;
  int a, b, c;
  for(auto t : vt){
    tie(a, b, c) = t;
    if(ff.at(a) == false || ff.at(b) == false) continue;
    if(d.at(a) + c < d.at(b)){
      ret = true;
      d.at(b) = d.at(a) + c;
    }
  }
  return ret;
}

int main(){
  int n, m, p;
  cin >> n >> m >> p;
  vector<tuple<int, int, int>> vt(m, tuple<int, int, int>());
  vector<vector<int>> to(n, vector<int>());
  vector<vector<int>> from(n, vector<int>());
  vector<bool> tc(n, false), fc(n, false), ff(n, false);
  rep(i, m){
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    c -= p;
    c *= -1;
    vt.at(i) = make_tuple(a, b, c);
    to.at(a).push_back(b);
    from.at(b).push_back(a);
  }
  dfs(to, tc, 0);
  dfs(from, fc, n-1);
  rep(i, n) ff.at(i) = tc.at(i) & fc.at(i);
  vector<int> d(n, INF);
  d.at(0) = 0;
  rep(i, n-1){
    if(update(vt, d, ff) == false) break;
  }
  if(update(vt, d, ff)) cout << -1 << endl;
  else cout << max(0, -1*d.at(n-1)) << endl;
  return 0;
}

Measured memory_bytes: 4032
#include<iostream>
#include<algorithm>
#include<queue>
#include<deque>
#include<vector>
#include<cstring>
using namespace std;
long long modpow(long long a, long long n, long long mod);
long long modinv(long long a, long long mod);
int main() {

	int n;
	string c;
	cin >> n;
	cin >> c;
	int sum = 0;
	int i, j;
	int s = 0;
	i = 0; j = n - 1;
	while (i < j) {
		if (c[i] == 'W') {
			if (c[j] == 'R') {
				c[i] = 'R';
				c[j] = 'W';
				i++;
				j--;
				sum++;
			}
			else {
				while (c[j] != 'R') {
					j--;
					if (j < 0 || j <= i) {
						cout << sum << endl;
						return 0;
					}
				}
				c[i] = 'R';
				c[j] = 'W';
				i++;
				j--;
				sum++;
			}
		}
		else {
			while (c[i] != 'W') {
				i++;
				if (i >= n || i >= j) {
					cout << sum << endl;
					return 0;
				}
			}
			if (c[j] == 'R') {
				c[i] = 'R';
				c[j] = 'W';
				i++;
				j--;
				sum++;
			}
			else {
				while (c[j] != 'R') {
					j--;
					if (j < 0 || j <= i) {
						cout << sum << endl;
						return 0;
					}
				}
				c[i] = 'R';
				c[j] = 'W';
				i++;
				j--;
				sum++;
			}
		}
	}

	cout << sum << endl;
	return 0;	
	
}

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// a^{-1} mod を計算する
long long modinv(long long a, long long mod) {
	return modpow(a, mod - 2, mod);
}


Measured memory_bytes: 3748
/*
   ??????????????¢?????´???????????¨??????????§????
   ?????????????????????????????????????????????????????§??????????????????
   ??¬?????????C?¨?????????????????????°?????? 
*/


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

//??????g????????????????????????
void insertionSort(int A[], int n, int g){
  for(int i=g;i<n;i++){
    int v = A[i];
    int j = i - g;
    while(j>=0&&A[j]>v){
      A[j+g] = A[j];
      j -= g;
      cnt++;
    }
    A[j+g] = v;
  }
}

void shellSort(int A[], int n){
  for(int h = 1;;){ //infinite
    if(h>n) break;
    G.push_back(h); //????????????????????????????????§??????????????????OK
    h = 3*h + 1;
  }
  
  for(int i = G.size()-1; i>=0; i--){ //??§???????????????
    insertionSort(A, n, G[i]);
  }
}

int main(){
  cin >> n; //scanf?
  for(int i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  cnt = 0;
  
  shellSort(A,n);
  
  //print
  cout << G.size() << endl;
  for(int i=G.size()-1;i>=0;i--){
    printf("%d",G[i]);
    if(i) printf(" "); //i==0?????¨???false
  }
  printf("\n");
  printf("%lld\n",cnt);
  for(int i=0;i<n;i++) printf("%d\n", A[i]);
  
  return 0;
}

Measured memory_bytes: 5196
#include<stdio.h>

#define MAX 100

int main(){
  
  int i,j,n,v,a;
  int arr[MAX];
  
  scanf("%d",&n);

  for(a=0;a<n;a++){
    scanf("%d",&arr[a]);
  }
  
  for(a=0;a<n-1;a++){
    printf("%d ",arr[a]);  
  }
  printf("%d\n",arr[n-1]);
  
  
  for(i=1;i<=n-1;i++){
    v = arr[i];
    j = i - 1;
    while(j>=0&&arr[j]>v){
      arr[j+1] = arr[j];
      j--;
      arr[j+1] = v;
    }
    for(a=0;a<n-1;a++){
      printf("%d ",arr[a]);  
    }
    printf("%d\n",arr[n-1]);
  }
  
  return 0;
}

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

typedef long long int ll;
typedef string str;

int main ()
{
	// ios::sync_with_stdio(0);
 //    cin.tie(0);
 //    cout.tie(0);
	ll t,n,m,k,i,a,b,j;
	cin >> n >> a >> b;
	m=n/(a+b);
	k=n%(a+b);
	i=m*a;
	if(k>=a)
	{
		i+=a;
	}
	else
		i+=k;
	cout << i << "\n";
	return 0;
}

Measured memory_bytes: 256
H,W,K=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())

pond=[]
for _ in range(H):
    pond.append(list(input()))

inf=10**7
cost=[[inf]*W for _ in range(H)]
cost[x1][y1]=0
from heapq import heapify,heappop,heappush
hq=[(0,x1,y1)]

while hq:
    t,x,y=heappop(hq)
    #北へ
    for i in range(1,K+1):
        if x-i<0 or pond[x-i][y]=="@" or cost[x-i][y]<t+1:
            break
        if cost[x-i][y]>t+1:
            cost[x-i][y]=t+1
            heappush(hq,(t+1,x-i,y))
    #東へ
    for i in range(1,K+1):
        if y+i>W-1 or pond[x][y+i]=="@" or cost[x][y+i]<t+1:
            break
        if cost[x][y+i]>t+1:
            cost[x][y+i]=t+1
            heappush(hq,(t+1,x,y+i))
    #南へ
    for i in range(1,K+1):
        if x+i>H-1 or pond[x+i][y]=="@" or cost[x+i][y]<t+1:
            break
        if cost[x+i][y]>t+1:
            cost[x+i][y]=t+1
            heappush(hq,(t+1,x+i,y))
    #西へ
    for i in range(1,K+1):
        if y-i<0 or pond[x][y-i]=="@" or cost[x][y-i]<t+1:
            break
        if cost[x][y-i]>t+1:
            cost[x][y-i]=t+1
            heappush(hq,(t+1,x,y-i))

if cost[x2][y2]==inf:
    print(-1)
    exit()  
print(cost[x2][y2])

Measured memory_bytes: 200752
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (a < b) {
            System.out.println("a < b");

        } else if (a > b) {
            System.out.println("a > b");

        } else {
            System.out.println("a == b");

        }
    }
}



Measured memory_bytes: 26240
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>
#include <cassert>
#include <cstdio>

using namespace std; using namespace placeholders;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector< int > VI;
typedef vector< vector< int > > VVI;
typedef vector< string > VS;
typedef stringstream SS;
typedef pair< int, int > PII;
typedef vector< pair< int, int > > VPII;
#define VT( T ) vector< T >
#define VVT( T ) vector< vector< T > >
#define LIM( T ) numeric_limits< T >

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }
template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; }
template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; };
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()
#define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )
#define DRANGE( c, p ) ( c ).begin(), ( c ).begin() + p, ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define PB push_back
#define EM emplace
#define EB emplace_back
#define BI back_inserter

#define EXIST( c, e ) ( ( c ).find( e ) != ( c ).end() )

#define MP make_pair
#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

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

	string s;
	cin >> s;

	s.erase( remove_if( ALL( s ), []( const char c ){ return c != 'A' && c != 'Z'; } ), s.end() );
	s.erase( unique( ALL( s ) ), s.end() );

	if ( SZ( s ) && s[0] != 'A' )
	{
		s.erase( 0, 1 );
	}
	if ( SZ( s ) && s.back() != 'Z' )
	{
		s.erase( SZ( s ) - 1 );
	}

	cout << ( SZ( s ) ? s : "-1" ) << endl;

	return 0;
}

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

#define REP(i,n) for (int (i) = 0; (i) <= (n); ++(i))
int main() {
    int n;
    int ret = 0;
    while(cin>>n){
        ret =0 ;
        REP(a, 9)REP(b, 9)REP(c, 9)REP(d, 9)if(a+b+c+d == n)ret++;
        cout<<ret<<endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
//#define int long long

using namespace std;
using LL = long long;
using P = pair<int, int>;

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

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e19;
const int MOD = 1e9 + 7;

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    LL dp[105][1 << (3*2)] = {0};

    string s = "ACGT";
    
    REP(i, 1 << (3*2)) dp[3][i] = 1;
    dp[3][0*16+2*4+1*1] = 0;
    dp[3][0*16+1*4+2*1] = 0;
    dp[3][2*16+0*4+1*1] = 0;

    FOR(i, 3, n)
    {
        REP(j, 1 << (3*2))
        {
            int a = j/4/4%4, b = j/4%4, c = j%4;
            REP(k, 4)
            {
                if(s[b] == 'A' && s[c] == 'G' && s[k] == 'C') continue;
                if(s[b] == 'G' && s[c] == 'A' && s[k] == 'C') continue;
                if(s[b] == 'A' && s[c] == 'C' && s[k] == 'G') continue;
                if(s[a] == 'A' && s[c] == 'G' && s[k] == 'C') continue;
                if(s[a] == 'A' && s[b] == 'G' && s[k] == 'C') continue;

                (dp[i+1][b*16+c*4+k] += dp[i][j]) %= MOD;
            }
        }
    }
    LL ans = 0;
    REP(i, 1 << (3*2))
    {
        (ans += dp[n][i]) %= MOD;
        int a = i/4/4%4, b = i/4%4, c = i%4;
        //cout << s[a] << " " << s[b] << " " << s[c] << " : " << dp[n][i] << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 * 3 + 10;
vector < int > edges[N];
int dist[N] , fix[N];
int main(){
	int n , m;
	cin >> n >> m;
	for(int i = 1; i <= m; i ++){
		int u , v;
		scanf("%d%d" , &u , &v);
		edges[u].push_back(v + n);
		edges[u + n].push_back(v + 2 * n);
		edges[u + 2 * n].push_back(v);
	}
	int S , T;
	cin >> S >> T;
	queue < pair < int , int > > Q;
	Q.push({S , 0});
	while(Q.size()){
		int u = Q.front().first;
		int d = Q.front().second;
		Q.pop();
		if(fix[u]) continue;
		fix[u] = 1;
		dist[u] = d;
		if(u == T) break;
		for(int i = 0; i < edges[u].size(); i ++)
			Q.push({edges[u][i] , d + 1});	
	}
	cout << (fix[T] ? dist[T] / 3 : -1) << "\n";
}

Measured memory_bytes: 18944
import Control.Monad
import Data.List

readInt = readLn :: IO Int
readInts = map read . words <$> getLine :: IO [Int]
readNInts = flip replicateM readInts

main :: IO ()
main = do
  [a, b, c] <- readInts
  putStrLn $ if b - a == c - b then "YES" else "NO"

Measured memory_bytes: 508
N, K = map(int, input().split())
if K == 0:
    print(N * N)
    exit()
ans = 0
for b in range(K + 1, N + 1):
    p = N // b
    ans += p * (b - K) + max(0, N - p * b - K + 1)
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include<unordered_map>
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define BUF 50
using namespace std;
ll MOD = 1e9 + 7;
ll A, B, C, D, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
ll ans = 0;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		while (a % 2 == 0) {
			a /= 2;
			ans++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

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

    cout << "ABC" << n << endl;

    return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<tuple<int,int,int>> array(n+1);
    for(int i=0;i<n;i++){
        int t,x,y;
        cin >> t >> x >> y;
        tuple<int,int,int> d = make_tuple(t,x,y);
        array.at(i+1) = d;
    }

    bool flag = true;
    for(int i=0;i<n;i++){
        tuple<int,int,int> now = array.at(i);
        tuple<int,int,int> next = array.at(i+1);
        int dx_plus_dy = abs(get<1>(next) - get<1>(now)) + abs(get<2>(next) - get<2>(now));
        int dt = get<0>(next) - get<0>(now);
        int zan = -dx_plus_dy + dt;
        //cout << zan <<endl;
        if(zan < 0 || zan % 2 == 1){
            flag = false;
            break;
        }  
    }
    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

}

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

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

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  string s;
  cin >> s;

  VI num(3,0);
  rep(i,s.size()) num[(int)(s[i] - 'a')]++;
  sort(all(num));
  rep(i,3){
    FOR(j,i+1,3){
      //cout << abs(num[i] - num[j]) << endl;
      if(abs(num[i] - num[j]) >= 2) {
        cout << "NO" << endl;
        return 0;
      }
    }
  }
  cout << "YES" << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define INF 1000000005
#define mod 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i = 0; i < (n); ++i) /*0からn-1までのrep*/
#define rrep(i,n) for(int i = 1; i <= (n); ++i) /*1からnまでのrep*/
#define drep(i,n) for(int i = (n)-1; i >= 0; --i) /*n-1から0までのrep*/
#define srep(i,s,t) for (int i = s; i < t; ++i) /*sからt-1までのrep*/
#define each(a,b) for(auto& (a): (b)) /*よくわからん*/
#define all(v) (v).begin(),(v).end() /*全選択*/
#define sz(v) (int)(v).size() /*大きさ*/
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) /*重複削除*/
#define cmx(x,y) x=max(x,y) /*最大値*/
#define cmn(x,y) x=min(x,y) /*最小値*/
#define rev(v) reverse((v).begin(),(v).end()); /*逆順*/
#define so(v) sort((v).begin(), (v).end()); /*ソート*/
#define yn {puts("Yes");}else{puts("No");} /*はい・いいえ*/
#define fi first
#define se second
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vd = vector<double>;
using vp = vector<P>;
using vs = vector<string>; 


int main() {
    long double t;
    ll a,ct;
    ct = 0;
    t = 100;
    cin >> a;
    while (t < a) {
        t = (t * 101)/100;
        t = floor(t);
        ct++;
    }
    cout << ct << endl;
    return 0;
}

Measured memory_bytes: 3648
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        new Main().solve();
    }

    private void solve() throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int n = Integer.parseInt(f.readLine());
        StringTokenizer tokenizer = new StringTokenizer(f.readLine());
        int[] ar = new int[n];
        for (int i = 0; i < n; i++) {
            ar[i] = Integer.parseInt(tokenizer.nextToken());
        }
        long sum = 0;
        long res = 0;
        int mod = 1000000007;
        for (int i = 0; i < n; i++) {
            res += sum * ar[i];
            res %= mod;
            sum += ar[i];
            sum %= mod;
        }

        out.println(res);

        out.close();
    }
}  

Measured memory_bytes: 55516
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int n=0, w=0, e=0, s=0;
    string t;
    cin >> t;
    for (int i = 0; i < t.size();i++){
        if(t[i]=='N')
            n++;
        if(t[i]=='S')
            s++;
        if(t[i]=='W')
            w++;
        if(t[i]=='E')
            e++;
    }
    //cerr << n << w << e << s << endl;
    if (n > 0 && e > 0 && w > 0 && s > 0)
        cout << "Yes" << endl;
    else if(n==0){
        if(s>0 || (w>0 && e==0) || (w==0 && e>0 ))
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
    else if(s==0){
        if(n>0 || (w>0 && e==0) || (w==0 && e>0 ))
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
    else if(w==0){
        if(e>0 || (n>0 && s==0) || (s==0 && n>0 ))
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
    else if(e==0){
        if(w>0 || (n>0 && s==0) || (s==0 && n>0 ))
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }


    return 0;
}

Measured memory_bytes: 256
k, a, b = map(int, input().split())
if a+2 >= b:
	print(k+1)
else:
	if k <= a-1:
		print(k+1)
	elif (k-a-1)%2 == 0:
		print(a + (b-a) * ((k-a+1) // 2))
	else:
		print(a+1 + (b-a) * ((k-a) // 2))


Measured memory_bytes: 38256
c = [list(map(int,input().split())) for _ in range(3)]

ok = True

lis = [[0,1],[1,2],[2,0]]

d = [[c[l[0]][i]-c[l[1]][i] for i in range(3)]for l in lis]
e = [[c[i][l[0]]-c[i][l[1]] for i in range(3)]for l in lis]

for i in range(3):
    if d[i].count(d[i][0])!=3:
        ok = False
    if e[i].count(e[i][0])!=3:
        ok = False
        
if ok:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 9228
n = gets.to_i
ar = gets.split.map(&:to_i)
colors = Array.new(8) {0}
monster = 0

ar.each do |num|
  div = num / 400
  if div < 8
    colors[div] = 1
  else
    monster += 1
  end
end

c = colors.count {|v| v == 1}
 
if c == 0 && monster > 0
  puts "1 #{c+monster}"
else
  puts "#{c} #{c+monster}"
end

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

using namespace std;

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

	long long int f[45];
	int n; cin >> n;

	f[0] = 1; f[1] = 1;
	for(int i=2;i<=n;i++) f[i] = f[i-1] + f[i-2];

	cout << f[n] << "\n";

	return 0;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
#define ll long long
#define C 1000000000000000000
using namespace std;
int main(void)
{
  ll a,b,c,k;
  cin>>a>>b>>c>>k;
  ll res=a-b;
  //cout<<res<<endl;
  if(abs(res)>C)
  {
    cout<<"Unfair";
  }
  else
  {
    if(k%2)
    {
      cout<<-1*res;
    }
    else
    {
      cout<<res;
    }
  }
}

Measured memory_bytes: 256
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;
#define INF 100000000
#define MAXN 100010
#define MAXQ 50010
typedef long long ll;

int S[MAXN], T[MAXQ];
int n, q;
int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> S[i];
    cin >> q;
    int ans = 0;
    for (int i = 0; i < q; i++) cin >> T[i];
    for (int i = 0; i < q; i++) {
        int l = 0, h = n, m;
        while (h >= l) {
            m = (h+l) / 2;
            if (S[m] > T[i]) h = m-1;
            else if (S[m] < T[i]) l = m+1;
            else break;
        }
        if (S[m] == T[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1744
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <cstdio>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

struct Edge {
	int src, dst, flow, rev;
	Edge() { }
	Edge(int src, int dst, int flow, int rev) {
		this->src = src;
		this->dst = dst;
		this->flow = flow;
		this->rev = rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &g, int s, int t, int flow) {
	g[s].push_back(Edge(s, t, flow, g[t].size()));
	g[t].push_back(Edge(t, s, 0, g[s].size() - 1));
}

int dfs(Graph &g, int s, int t, vector<int> &level, vector<int> &iter, int f) {
	if (s == t) return f;
	
	for (int &i = iter[s]; i < g[s].size(); i++) {
		Edge e = g[s][i];
		if (e.flow <= 0) continue;
		if (level[e.dst] != level[s] + 1) continue;
		
		int res = dfs(g, e.dst, t, level, iter, min(f, e.flow));
		if (res == 0) continue;
		
		//s -> e.dst
		g[s][i].flow -= res;
		g[e.dst][g[s][i].rev].flow += res;
		return res;
	}
	return 0;
}

int maxflow(Graph g, int s, int t) {
	int n = g.size();
	vector<int> level(n);
	
	int ret = 0;
	while (true) {
		int i;
		rep(i, n) level[i] = -1;
		
		queue<int> que;
		que.push(s);
		level[s] = 0;
		while (!que.empty()) {
			int v = que.front(); que.pop();
			rep(i, g[v].size()) {
				Edge e = g[v][i];
				if (e.flow <= 0) continue;
				if (level[e.dst] == -1) {
					level[e.dst] = level[v] + 1;
					que.push(e.dst);
				}
			}
		}
		if (level[t] == -1) break;
		
		vector<int> iter(n, 0);
		while (true) {
			int flow = dfs(g, s, t, level, iter, 1e+8);
			if (flow == 0) break;
			ret += flow;
		}
	}
	return ret;
}

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

int m, n;
int b[500];
int r[500];

int main() {
	while (cin >> m >> n) {
		if (!m) break;
		int i, j;
		rep(i, m) cin >> b[i];
		rep(i, n) cin >> r[i];
		
		Graph g;
		
		g.resize(m + n + 2);
		rep(i, m) add_edge(g, 0, i + 1, 1);
		rep(i, m) {
			rep(j, n) {
				if (gcd(b[i], r[j]) > 1) {
					add_edge(g, i + 1, m + 1 + j, 1);
				}
			}
		}
		rep(i, n) {
			add_edge(g, m + 1 + i, m + 1 + n, 1);
		}
		
		int res = maxflow(g, 0, m + n + 1);
		cout << res << endl;
	}
	return 0;
}


Measured memory_bytes: 12160
program sample
    implicit none
  
    integer(8) :: i,j,m,n,b(100000)
    
    integer(8),allocatable :: a(:),y(:)
  
    read(*,*) n
    do i=1,100000
        b(i)=0
    end do
    allocate(a(n))
    read(*,*)a
    do i=1,n
        m=a(i)
        b(m)=b(m)+1
    end do
    m=0
    do i=1,100000
        if (b(i)>0)then
            m=m+1
        end if
    end do
    if (mod(m,2)==0)then
        m=m-1
    end if
    write(*,*) m
    deallocate(a)
    stop
end program sample
  



Measured memory_bytes: 4572
#include<stdio.h>
#include<iostream>
#include<cassert>
#include<stack>
#include<algorithm>
#define MAX 505
#define BLOCK 0

using namespace std;

struct Rectangle{ int height;  int pos; };

int getLargestRectangle( int size, int buffer[]){
    stack<Rectangle> S;
    int maxv = 0;
    buffer[size] = 0;
    
    for ( int i = 0; i <= size; i++ ){
        Rectangle rect;
        rect.height = buffer[i];
        rect.pos = i;
        if ( S.empty() ){
            S.push( rect );
        } else {
            if ( S.top().height < rect.height ){
                S.push( rect );
            } else if ( S.top().height > rect.height ) {
                 int target = i;
                 while ( !S.empty() && S.top().height >= rect.height){
                     Rectangle pre = S.top(); S.pop();
                     int area = pre.height * (i - pre.pos);
                     maxv = max( maxv, area);
                     target = pre.pos;
                 }
                 rect.pos = target;
                 S.push(rect);
             }
         }
     }
     return maxv;
 }

int H, W;
int buffer[MAX][MAX];
int T[MAX][MAX];
 
int getLargestRectangle(){
    for ( int i = 0; i < H; i++ ){
	for ( int j = 0; j < W; j++ ){
	    T[i][j] = 0;
	}
    }
     
    for ( int j = 0; j < W; j++ ){
	int sequence = 0;
	for ( int i = 0; i < H; i++ ){
	    if ( buffer[i][j] == BLOCK ){
		sequence = T[i][j] = 0;
	    } else {
		T[i][j] = ++sequence;
	    }
	}
    }
    
    int maxv = 0;
    for ( int i = 0; i < H; i++ ){
	maxv = max( maxv, getLargestRectangle( W, T[i] ) );
    }
    
    return maxv;
}

int main(void){
    while(1){
	cin >> H >> W;
	if ( H == 0 && W == 0) break;

	char ch;
	for ( int i = 0; i < H; i++ ){
	    for ( int j = 0; j < W; j++ ){
		cin >> ch;
		if ( ch == '*' ) buffer[i][j] = 0;
		else buffer[i][j] = 1;
	    }
	}
	cout << getLargestRectangle() << endl;
    }
    
    return 0;
}

Measured memory_bytes: 2888
#include <iostream>
#include <fstream>
#include <sstream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>

//#define DEBUG 1

#define int long long
#define for0(i,n) for (int i=0; i<n; i++)
#define iter(c) for(auto it=c.begin(); it!=c.end(); it++)
#define vec(x) vector< x >
#define pb push_back
#define ms(a,z) memset(a,z,sizeof(a));
#define mp make_pair
#define X first
#define Y second
#define sqr(x) 1LL*(x)*(x)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#ifdef int
#define read(x) scanf("%lld",&x);
#else
#define read(x) scanf("%d",&x);
#endif

#ifdef DEBUG
#define nl cout<<"\n";
#define pr(x) cout<<(x)<<" ";
#define prl(x) cout<<#x " = "<<x<<endl;
#define prp(x) cout<<"("<<(x).first<<" "<<(x).second<<") ";
#define printv(v) {for(int _=0; _<sz(v); _++) cout<<v[_]<<" "; cout<<"\n";}
#define printa(a,s) {for (int _=0; _<s; _++) cout<<a[_]<<" "; cout<<"\n";}
#define print2D(a,m,n) {for (int _=0; _<m; _++) {for (int __=0; __<n; __++) cout<<a[_][__]<<" "; cout<<"\n";} cout<<"\n";}
#define debug cout<<"ok at line "<<__LINE__<<endl;
#else
#define nl
#define pr(x)
#define prl(x)
#define prp(x)
#define printv(v)
#define printa(a,s)
#define print2D(a,m,n)
#define debug
#endif

using namespace std;

typedef long long ll;

const int INF = 2147483647;
const long long INFL = 9223372036854775807LL;
const double EPSILON = 0.00000001;
const long long MOD = 1000000007;

int freq[26];

int32_t main()
{
    #ifdef DEBUG
    freopen("B.txt","r",stdin);
    //freopen("","w",stdout);
    #endif

    ms(freq,0);
    string s; 
    cin >> s;
    int n = s.length();
    for0(i,n) {
        freq[s[i]-'a']++;
    }
    
    ll ans = 0;
    for0(i,n) {
        ans += n-freq[s[i]-'a'];
    }
    ans /= 2;
    ans += 1;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
int main(){
	int N;
	int check = 0;
	scanf("%d", &N);
	char S[N];
	scanf("%s", S);
	int i;
	if(N%2==1){
		printf("No\n");
		return 0;
	}
	
	if(N%2==0){
		for(i=0;S[i]!='\0';i++){
			if(S[i]== S[(N/2)+ i]){
				check++;
			}
		}
		if(check == N/2){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
		}	

	
	
	return 0;
}

Measured memory_bytes: 1628
#include <bits/stdc++.h>
using i64 = long long;

int main() {
    int h, n;
    std::cin >> h >> n;
    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) std::cin >> a[i] >> b[i];

    constexpr int inf = std::numeric_limits<int>::max() / 3;
    std::vector<int> dp(h + 11000, inf);
    dp[0] = 0;
    for (int i = 0; i <= h; i++) for (int j = 0; j < n; j++) {
        if (i + a[j] < dp.size()) dp[i + a[j]] = std::min(dp[i + a[j]], dp[i] + b[j]);
    }

    int ret = *std::min_element(dp.begin() + h, dp.end());
    std::cout << ret << std::endl;

    return 0;
}


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

ll n, p;
ll a[N], memo[5][N];
bool even, odd;

ll exp(ll a, ll b) {
    if(b == 1) return a;
    if(memo[a][b] != -1) return memo[a][b];
    if(b & 1) return memo[a][b] = exp(a, b / 2) * exp(a, b / 2) * a;
    else return memo[a][b] = exp(a, b / 2) * exp(a, b / 2);
}

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

    cin >> n >> p;
    for(ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    memset(memo, -1, sizeof(memo));
    even = true, odd = false;
    for(ll i = 1; i <= n; i++) {
        if(a[i] % 2 == 1) {
            even = false;
            odd = true;
        }
    }
    if(even) {
        if(p == 0) cout << exp(2, n) << "\n";
        else cout << "0\n";
    } else if(odd) {
        cout << exp(2, n - 1) << "\n";
    }
}

Measured memory_bytes: 3600
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import numpy as np


def main():
    W, H, N = map(int, input().split())
    result = np.zeros((W, H))

    for _ in range(N):
        X, Y, A = map(int, input().split())
        if A == 1:
            result[:X, :] = 1
        elif A == 2:
            result[X:, :] = 1
        elif A == 3:
            result[:, :Y] = 1
        elif A == 4:
            result[:, Y:] = 1
    print(np.count_nonzero(1 - result))


if __name__ == "__main__":
    main()


Measured memory_bytes: 12600
#include <bits/stdc++.h> 
 
#define INF (1<<31)//INT_MAX/2
#define MOD 1000000007
 
using ll  = long long;
using ull = unsigned long long;
 
int main(int argc, char *argv[])
{
    std::string S;
    std::cin >> S;

    int ans = 0;
    for (int i = 0; i < 4; i++) {
        if (S[i] == '+') {
            ans++;
        } else {
            ans--;
        }
    }

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define db double
int A, B, C, D, E, F;
bool wtr[31] = {true};
bool sgr[3010] = {true};

int main(){
    cin >> A >> B >> C >> D >> E >> F;
    
    for(int i = 0; i <= F / 100; i++){
        if(!wtr[i]) continue;
        if(i + A <= F / 100) wtr[i + A] = true;
        if(i + B <= F / 100) wtr[i + B] = true;
    }

    for(int i = 0; i <= F; i++){
        if(!sgr[i]) continue;
        if(i + C <= F) sgr[i + C] = true;
        if(i + D <= F) sgr[i + D] = true;
    }
    int a = A * 100;
    int b = 0;
    double cnc = 0;
    for(int i = 1; i < 31; i++){
        if(!wtr[i]) continue;
        for(int j = F; j >= 0; j--){
            if(!sgr[j]) continue;
            if(j + i * 100 > F) continue;
            if(j > i * E) continue;
            double c = (db)j / ((db)i * (db)100 + (db)j);
            if(c > cnc) a = i * 100, b = j, cnc = c;
        }
    }
    cout << a + b << " " << b << endl;
    return 0;
}

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

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 200007;

int n,val[_];
multiset<int> mp;

int main()
{
	n=ty();
	for(int i=1;i<=n;i++)val[i]=ty();

	for(int i=1;i<=n;i++)mp.emplace(val[i]);
	
	int ans=0;
	while(!mp.empty())
	{
		int a=*mp.rbegin();
		mp.erase(--mp.end());
		int x=1;while(x<=a)x<<=1;
		int b=x-a;
		if(mp.find(b)!=mp.end())ans++,mp.erase(mp.find(b));
	}

	printf("%d\n",ans);
	
	return 0;
}


Measured memory_bytes: 10368