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

#define int long long

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

  int N;
  cin >> N;

  string s;
  cin >> s;

  int cnt[4] = {};
  for ( int i = 0; i < N; i++ ) {
    if ( 'A' <= s[i] && s[i] <= 'M' ) cnt[0]++;
    if ( 'N' <= s[i] && s[i] <= 'Z' ) cnt[1]++;
    if ( 'a' <= s[i] && s[i] <= 'm' ) cnt[2]++;
    if ( 'n' <= s[i] && s[i] <= 'z' ) cnt[3]++;
  }

  int mi[4];
  mi[0] = mi[1] = min(cnt[0], cnt[1]);
  mi[2] = mi[3] = min(cnt[2], cnt[3]);

  string ans = "";
  for ( int i = 0; i < N; i++ ) {
    if ( 'A' <= s[i] && s[i] <= 'M' && mi[0] ) mi[0]--;
    else if ( 'N' <= s[i] && s[i] <= 'Z' && mi[1] ) mi[1]--;
    else if ( 'a' <= s[i] && s[i] <= 'm' && mi[2] ) mi[2]--;
    else if ( 'n' <= s[i] && s[i] <= 'z' && mi[3] ) mi[3]--;
    else ans.push_back(s[i]);    
  }

  cout << ans.size() << endl;
  cout << ans << endl;
  
  return 0;
}



Measured memory_bytes: 3340
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<pair<int,int> >G[1<<17];
pair<int,int>dp1[1<<17];
pair<int,int>dfs1(int u,int p)
{
	pair<int,int>ret;
	ret.first=ret.second=0;
	for(pair<int,int>q:G[u])
	{
		if(q.first==p)continue;
		pair<int,int>now=dfs1(q.first,u);
		ret.first=max(ret.first,now.first+q.second);
		ret.second=max(ret.second,max(now.second,q.second));
	}
	dp1[u]=ret;
	return ret;
}
int ans;
void dfs2(int u,int p,pair<int,int>P)
{
	vector<pair<pair<int,int>,int> >A;
	A.push_back(make_pair(P,-1));
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i].first;
		if(v==p)continue;
		A.push_back(make_pair(make_pair(dp1[v].first+G[u][i].second,max(dp1[v].second,G[u][i].second)),i));
	}
	sort(A.rbegin(),A.rend());
	pair<int,int>dmax1,dmax2,emax1,emax2;
	dmax1=dmax2=emax1=emax2=make_pair(0,-1);
	while(A.size()<3)A.push_back(make_pair(make_pair(0,0),-(int)A.size()-1));
	for(int i=0;i<A.size();i++)
	{
		ans=max(ans,A[i].first.second+A[i==0?2:0].first.first+A[i==1?2:1].first.first);
		if(dmax1.first<=A[i].first.first)
		{
			dmax2=dmax1;
			dmax1=make_pair(A[i].first.first,A[i].second);
		}
		else if(dmax2.first<=A[i].first.first)
		{
			dmax2=make_pair(A[i].first.first,A[i].second);
		}
		if(emax1.first<=A[i].first.second)
		{
			emax2=emax1;
			emax1=make_pair(A[i].first.second,A[i].second);
		}
		else if(emax2.first<=A[i].first.second)
		{
			emax2=make_pair(A[i].first.second,A[i].second);
		}
	}
	for(int i=0;i<G[u].size();i++)
	{
		if(G[u][i].first==p)continue;
		dfs2(G[u][i].first,u,make_pair(G[u][i].second+(dmax1.second==i?dmax2.first:dmax1.first),max(G[u][i].second,emax1.second==i?emax2.first:emax1.first)));
	}
}
main()
{
	cin>>N;
	for(int i=1;i<N;i++)
	{
		int p,w;cin>>p>>w;
		G[p].push_back(make_pair(i,w));
		G[i].push_back(make_pair(p,w));
	}
	dfs1(0,-1);
	dfs2(0,-1,make_pair(0,0));
	cout<<ans<<endl;
}



Measured memory_bytes: 33476
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

if __name__ == '__main__':
    x = [int(i) for i in input().split()]
    a = (x[0]-1) // x[2]
    b = x[1] // x[2]

    print(b-a)

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { os << p.first << ' ' << p.second; return os; }

inline bool is_prime(i32 n) {
  if (n < 2) {
    return 0;
  }
  for (i32 i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

unordered_set<int> prime_list(i32 n) {
  unordered_set<int> primes;
  vector<bool> f(n, true);
  f[0] = f[1] = false;
  repi(i, 2, n) {
    if (!f[i]) continue;
    primes.insert(i);
    for (int j = i * 2; j < n; j += i) {
      f[j] = false;
    }
  }
  return primes;
}

void solve() {
  auto primes = prime_list(100010);
  vi32 sums(100010);
  for (int i = 1; i <= 100000; i += 2) {
    if (primes.count(i) > 0 && primes.count((i + 1) / 2) > 0) sums[i] = 1;
  }
  rep(i, 100000) sums[i + 1] += sums[i];

  int q; cin >> q;
  while (q--) {
    int l, r; cin >> l >> r;
    cout << sums[r] - sums[l - 1] << '\n';
  }
}


Measured memory_bytes: 1536
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

char guess(char ans, char before, char animal)
{
    char other = before == 'S' ? 'W' : 'S';
    if (animal == 'S') {
        return ans == 'o' ? before : other;
    } else {
        return ans == 'x' ? before : other;
    }
};

bool check(int i, string& Answer, const string& S)
{
    char now = guess(S[i - 1], Answer[i - 2], Answer[i - 1]);
    if (i == S.size()) {
        if (now != Answer[0])
            return false;

        now = guess(S[0], Answer.back(), Answer[0]);
        return now == Answer[1];
    }

    Answer[i] = now;
    return check(i + 1, Answer, S);
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int N;
    string S;
    cin >> N >> S;
    string Answer(N, '_');
    for (char c1 : "SW")
        for (char c2 : "SW") {
            Answer[0] = c1;
            Answer[1] = c2;
            if (check(2, Answer, S)) {
                cout << Answer << endl;
                return 0;
            }
        }

    cout << -1 << endl;
    return 0;
};

Measured memory_bytes: 640
/**
*    created: 12.05.2020 09:34:32
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
const int inf =1000000000;

int main() {
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    rep(i, n) cin >> l[i] >> r[i];
    int ans=0;
    rep(i,n){
        ans+= r[i] - l[i]+1;
    }
    cout << ans   << endl;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    a = input()
    b = input()
    c = input()
    ans = 0

    for i in range(n):
        if a[i] == b[i] and b[i] == c[i]:
            continue
        elif a[i] == b[i] and b[i] != c[i]:
            ans += 1
        elif b[i] == c[i] and c[i] != a[i]:
            ans += 1
        elif c[i] == a[i] and a[i] != b[i]:
            ans += 1
        else:
            ans += 2

    print(ans)


if __name__ == "__main__":
    main()


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

using namespace std;

int main()
{
  int data[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k;

  cin >> k;

  cout << data[k - 1];

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
int x,y;
int main(void) {
	void solve();
	solve();
	return 0;
}
LL C1(int n,int m) {
	if(m > n / 2) m = n - m;         // 由性质 1 得到的
	LL a = 1,b = 1;
	for(int i = 1; i <= m; i ++) {
		a = a *( n + 1 - i) % MOD;
		b = b * i % MOD;
		if(a % b == 0) {
			a /= b;
			b = 1;
		}
	}
	return a / b % MOD;
}
LL mod = 1000000007;
const int maxn = 1000010;
LL qpow(LL a,LL x) {
	LL ret=1;
	while (x) {
		if (x&1)
			ret = ret*a%mod;
		a=a*a%mod;
		x>>=1;
	}
	return ret;
}
LL fac[maxn],inv[maxn];
LL init() {
	fac[0]=1;
	for (int i=1; i<maxn; i++)
		fac[i]=fac[i-1]*i%mod;
	inv[maxn-1]=qpow(fac[maxn-1],mod-2);
	for (int i=maxn-2; i>=0; i--)
		inv[i]=inv[i+1]*(i+1)%mod;
	return 0;
}
LL C(LL n,LL m) {
	if (n<m) return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

void solve() {
	bool flag = true;
	int k,t;
	init();
	scanf("%d%d",&x,&y);
	for(int i = 0; i <= x; i ++) {
		if(2 * y - 3 * i == x) {
			t = y - 2 * i;
			k = i;
			flag = false;
			break;
		}
	}
	
	if(flag) printf("0\n");
	else printf("%lld\n",C(k + t,k));
	return ;
}

Measured memory_bytes: 15872
#include <iostream>

using namespace std;

int main() {
    int K, S;
    cin >> K >> S;
    int cou = 0;
    for (int X = 0; X <= K; X++) {
        for (int Y = 0; Y <= K; Y++) {
                int A = S - X - Y;
                if (0 <= A&&A <= K) {
                    cou++;
                }
            }
        }
    cout << cou++ << endl;
}

Measured memory_bytes: 256
#![allow(non_snake_case)]
#[allow(unused_imports)]
use std::io::{self, Write};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };
    ($next:expr, char) => {
        read_value!($next, String).chars().collect::<Vec<char>>()[0]
     };
    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
     };
    ($next:expr, isize1) => {
        read_value!($next, isize) - 1
    };
     ($next:expr, $t:ty) => {
         $next().parse::<$t>().expect("Parse error")
    };
}
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}
#[allow(dead_code)]
const MOD: usize = 1000000007;
#[allow(dead_code)]
fn to_num(c: char) -> i64 {
    c as i64 - 48
}


fn main() {
    input!{
        a: usize,
        s: String,
    }
    println!("{}", if a >= 3200 {s} else {"red".to_string()});
}

Measured memory_bytes: 4352
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

S = raw_input()
if S[0] == S[1] or S[1] == S[2] or S[2] == S[3]:
    print "Bad"
else:
    print "Good"

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

int main(){
  int i,N,array[101],M,array2[101],array3[101],array4[101]={},array5[101],j;
  cin>>N;
  for(i=0;i<N;i++){
    cin>>array[i];
    array5[i]=array[i];
  }
  cin>>M;
  for(i=0;i<M;i++){
    cin>>array2[i]>>array3[i];
  }
  for(i=0;i<M;i++){
    array[array2[i]-1]=array3[i];
    for(int j=0;j<N;j++){
      array4[i]+=array[j];
    }
    cout<<array4[i]<<endl;
    array[array2[i]-1]=array5[array2[i]-1];
  }
}


Measured memory_bytes: 256
X = int(input())
end = 0
for a in range(1000):
    for b in range(1000):
        if a**5 - b**5 == X:
            print(a, b)
            end = 1
            break
        elif a**5 + b**5 == X:
            print(a, -b)
            end = 1
            break
        
    if end == 1:
        break
        
        

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

int main(int argc, char const* argv[]) {
    int a, b;
    cin >> a >> b;
    std::vector<int> hs(999);
    hs[0] = 1;
    for (int i = 1; i < 999; ++i) {
        hs[i] = i + 1 + hs[i - 1];
    }
    int diff = b - a;
    int right = hs[diff - 1];
    std::cout << right - b << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
int board[100][100];
bool vst[100][100];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int w,h,xs,ys,xg,yg,n;
bool dfs(int x,int y) {
	if(x==xg && y==yg)
		return true;
	vst[x][y]=true;
	for(int i=0;i<4;i++) {
		int nx=x+dx[i],ny=y+dy[i];
		if(0>nx||nx>=w||0>ny||ny>=h)
			continue;
		if(board[nx][ny]!=board[xs][ys])
			continue;
		if(vst[nx][ny])
			continue;
		if(dfs(nx,ny)) return true;
	}
	return false;
}
int main() {
	while(scanf("%d %d",&w,&h),w|h) {
		scanf("%d %d",&xs,&ys); xs--;ys--;
		scanf("%d %d",&xg,&yg); xg--;yg--;
		scanf("%d",&n);
		memset(board,0,sizeof(board));
		memset(vst,0,sizeof(vst));
		for(int i=0;i<n;i++) {
			int c,d,x,y;
			scanf("%d %d %d %d",&c,&d,&x,&y); x--;y--;
			if(d==0) {
				for(int i=0;i<4;i++) for(int j=0;j<2;j++)
					board[x+i][y+j]=c;
			}else {
				for(int i=0;i<2;i++) for(int j=0;j<4;j++)
					board[x+i][y+j]=c;
			}
		}
		printf("%s\n",dfs(xs,ys)?"OK":"NG");
	}
}

Measured memory_bytes: 1076
#include <bits/stdc++.h>
#pragma gcc optimize("ofast")
using namespace std;

#define ll long long //data types used often, but you don't want to type them time by time
#define ull unsigned long long
#define ui unsigned int
#define mod 998244353
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0); //to synchronize the input of cin and scanf
#define INF LONG_MAX
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(int x=j;x<n;x++)
#define all(x) (x).begin(), (x).end()

typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;

bool prime(ll n)
{
	if(n<=1)return false;
	if(n<=3)return true;
	if(n%2==0||n%3==0)return false;
	for(ll i=5;i*i<=n;i+=6)
	{
		if(n%i==0||n%(i+2)==0)return false;
	}
	return true;
}

ll modexp(ll a,ll b,ll m)
{
	ll r=1;
	a=a%m;
	while(b>0)
	{
		if(b&1)
		    r=(r*a)%m;
		b>>1;
		a=(a*a)%m;
	}
	return r%m;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	ll n,m; cin>>n>>m;
	ll x = (n*(n-1))/2+(m*(m-1))/2;
	cout<<x<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 20000
int a[MAXN+5],b[MAXN+5];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=i*(n+1),b[i]=(n-i+1)*(n+1);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        a[x]-=n-i+1;
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<' ';
    cout<<endl;
    for(int i=1;i<=n;i++)
        cout<<b[i]<<' ';
    return 0;
}

Measured memory_bytes: 768
a,b,c = map(int,input().split())
k = int(input())
p = 0
for i in range(k+1):
	if c*(2**i) > b*(2**(k-i)) and b*(2**(k-i)) > a:
		p += 1
		break
if p == 1:
	print('Yes')
else:
	print('No') 

Measured memory_bytes: 9180
package main

import (
  "bufio"
  "fmt"
  "os"
  "sort"
  "strconv"
)

//============================================================
var sc = bufio.NewScanner(os.Stdin)

func cout(out string) { fmt.Println(out) }
func setScSplit()     { sc.Split(bufio.ScanWords) }
func stoi(str string) int {
  num, _ := strconv.Atoi(str)
  return num
}
func itos(num int) string {
  str := strconv.Itoa(num)
  return str
}
func gsf() string {
  sc.Scan()
  return sc.Text()
}
func gif() int {
  i := stoi(gsf())
  return i
}
func gff() float64 {
  f, _ := strconv.ParseFloat(gsf(), 64)
  return f
}
func uniq(list []int) []int {
  m := make(map[int]struct{}) // 空のstructを使う
  for _, ele := range list {
    m[ele] = struct{}{} // m["a"] = struct{}{} が二度目は同じものとみなされて重複が消える。
  }
  uni := []int{}
  for i := range m {
    uni = append(uni, i)
  }
  return uni
}
func usort(list []int) []int {
  sort.Sort(sort.IntSlice(list))
  return list
}
func dsort(list []int) []int {
  sort.Sort(sort.Reverse(sort.IntSlice(list)))
  return list
}
func push(t *[]int, x int) {
  tmp := *t
  *t = append(tmp, x)
}
func pop(t *[]int) int {
  tmp := *t
  x := tmp[len(tmp)-1]
  *t = tmp[:len(tmp)-1]
  return x
}
func deq(t *[]int) int {
  tmp := *t
  x := tmp[0]
  *t = tmp[1:]
  return x
}

//=============================================================

func main() {
  setScSplit()
  a, b, c := gif(), gif(), gif()
  x := gif()
  cnt := 0
  for i := 0; i <= a; i++ {
    for j := 0; j <= b; j++ {
      for k := 0; k <= c; k++ {
        if i*500+j*100+k*50 == x {
          cnt++
        }
      }
    }
  }
  cout(itos(cnt))
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp setprecision
#define pb(x) push_back(x)
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const ld EPS = 1e-10;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    int N;
    cin >> N;
    int a[N], b[N];
    string s;
    cin >> s;
    rep(i, N) a[i] = (s[i] == 'x');
    rep(p, 2) rep(q, 2){
        b[0] = p, b[1] = q, b[2] = a[1]^p^q;
        //b[i]を順に決めていく
        rep2(i, 3, N-1){
            b[i] = b[i-3]^(a[i-1]!=a[i-2]);
        }
        bool able = true;
        rep(i, N){
            if(b[(i+N-1)%N]^b[i]^b[(i+1)%N] != a[i]) able = false;
        }
        if(able){
            rep(i, N){
                if(b[i]) cout << 'W';
                else cout << 'S';
            }
            cout << endl;
            return 0;
        }
        elif(p&q) cout << -1 << endl;
    }
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define prArr(Arr,n) for(int _=0;_<n;_++)   cout<<(Arr)[_]<<" ";
#define fi first
#define s second
using namespace std;
const int INF=(int)0x3f3f3f3f;
const int MOD=(int)1e9+7;
const double eps=1e-9;
int n;
vector<pair<pair<int,int>,pair<int,int>>> v;
double f(double t)
{
    double inf=(double)INF*INF;
    double minX=inf,minY=inf,maxX=-inf,maxY=-inf;
    for(int i=0;i<n;i++){
        double x=v[i].fi.fi+t*v[i].s.fi,y=v[i].fi.s+t*v[i].s.s;
        minX=min(minX,x),maxX=max(maxX,x);
        minY=min(minY,y),maxY=max(maxY,y);
    }
    //cout<<minX<<" "<<maxX<<" "<<minY<<" "<<maxY<<"\n";
    return (maxX-minX)*(maxY-minY);
}
double ternary_search(double l, double r) {

    for(int i=0;i<1000;i++) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        double f1 = f(m1);      //evaluates the function at m1
        double f2 = f(m2);      //evaluates the function at m2
        //cout<<m1<<" "<<f1<<" "<<m2<<" "<<f2<<"\n";
        if (f1 < f2)
            r = m2;
        else
            l = m1;
    }
    return f(l);                    //return the maximum of f(x) in [l, r]
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    char c;
    cin>>n;
    v.resize(n);
    for(int i=0;i<n&&cin>>v[i].fi.fi>>v[i].fi.s>>c;i++)
    {
        if(c=='U')v[i].s={0,1};
        if(c=='D')v[i].s={0,-1};
        if(c=='R')v[i].s={1,0};
        if(c=='L')v[i].s={-1,0};
    }
    cout<<setprecision(10)<<fixed<<ternary_search(0,1e9);
    return 0;
}



Measured memory_bytes: 4792
import java.util.*;

class Main {
  public static void main (String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    for (int ii = 0; ii < n; ii++) {
      System.out.printf("Case %d:\n", ii + 1);
      int s = scanner.nextInt();
      for (int jj = 0; jj < 10; jj++) {
        String str = String.format("%08d", s * s);
        s = Integer.parseInt(str.substring(2, 2 + 4));
        System.out.println(s);
      }
    }
  }
}

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

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define minvec(v) *min_element(all(v))
#define maxvec(v) *max_element(all(v))
#define sumvec(v) accumulate(all(v),0)
#define mapmax(v) v.rbegin()->first
#define mapmin(v) v.begin()->first
#define pb push_back
#define pf push_front
#define mod 1000000007
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))
#define zero(x,n) setw(x) << setfill('0') << n

typedef long long ll;

typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<string> vs;

typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;

const double pi = acos(-1.0);

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

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

void YES(bool b) {cout << (b?"YES\n":"NO\n");}
void Yes(bool b) {cout << (b?"Yes\n":"No\n");}
void yes(bool b) {cout << (b?"yes\n":"no\n");}
void Yay(bool b) {cout << (b?"Yay!\n":":(\n");}

ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

ll n;

void dfs(string s,char m){
	if((int)s.length()==n) cout << s << endl;
	else{
		for(char c='a';c<=m;c++){
			if(c==m) dfs(s+c,(char)(m+1));
			else dfs(s+c,m);
		}
	}
}

int main()
{
	cin >> n;
	dfs("",'a');
	return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()		//sort(all(vi S)) sort(all(string S))
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

using P = pair<int, int>;		//P.first, P.second
typedef long long ll;
typedef vector<int> vi;
typedef set<int> seti;
typedef vector<string> vs;

const int MOD = 1e9+7;
const int INF = 1e9;

int main() {
	int N;
	cin>>N;
	vector<int> W(N);
	int sum_W = 0;
	rep(i,N){
		cin>>W[i];
		sum_W +=W[i];
	}
	int ans = sum_W;
	int w1 = 0;
	int w2 = sum_W;
	rep(i,N){
		w1 += W[i];
		w2 -= W[i];
		cerr<<w1<<" "<<w2<<endl;
		ans = min(ans,abs(w2-w1));
	}
	
	cout<<ans<<endl;
}

Measured memory_bytes: 256
N,M=map(int,input().split())
H=list(map(int,input().split()))
H.insert(0,0)
path=[[] for i in range(N+1)]

for i in range(M):
    A,B=map(int,input().split())
    path[A].append(B)
    path[B].append(A)

ans = 0
for i in range(1,N+1):
    if path[i] == []:
        ans += 1
    else:
        hi=H[i]
        f = True
        for t in path[i]:
            if hi <= H[t]:
                f = False
                break
        if f:
            ans += 1

print(ans)





Measured memory_bytes: 92656
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = Integer.parseInt(sc.next()), b = Integer.parseInt(sc.next());
    if ((a*b)%2 == 0){System.out.println("Even");}
    else{System.out.println("Odd");}
  }
}

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

#define rep(i,n) for (int i = 0; i < (n); i++) 
 
int main() {
    int n,k,a,count = 0;

    cin >> n >> k;

    vector<int> d(k),okasi(n,0);

    rep(i,k){
        cin >> d[i];
        rep(j,d[i]){
            cin >> a;
            okasi[a-1] = 1;
        }
    }

    for (auto i = okasi.begin(); i !=okasi.end(); ++i)
    {
        if(*i == 0){
            count++;
        }
    }
    
    cout << count << endl;
}

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

}


Measured memory_bytes: 1024
#include <cstdio>
int gcd (int a, int b) {
	while (true) {
		if (a > b)
			a -= b;
		else if (a < b)
			b -= a;
		else
			break;
	}
	return a;
}
int lcm (int a, int b) {
	int sum_a = a;
	int sum_b = b;
	while (true) {
		if (sum_a > sum_b)
			sum_b += b;
		else if (sum_a < sum_b)
			sum_a += a;
		else
			break;
	}
	return sum_a;
}
int main ( int argc, char *argv[] ) {
	using namespace std;
	int a, b;
	while (EOF != fscanf(stdin, "%d %d\n", &a, &b)) {
		printf("%d %d\n", gcd(a, b), lcm(a, b));
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int64_t MOD = 998244353;

int main()
{
  int64_t N, d, maxd = 0, ans = 1;
  cin >> N;
  vector<int64_t> D(N + 1), Count(N + 1, 0);
  for (int64_t i = 1; i <= N; i++)
  {
    cin >> d;
    D.at(i) = d;
    Count.at(d)++;
    if (d > maxd)
      maxd = d;
  }

  for (int64_t i = 1; i <= N; i++)
  {
    if ((i == 1 && D.at(i) != 0) || (D.at(i) == 0 && i != 1))
    {
      cout << 0 << endl;
      return 0;
    }
  }

  for (int64_t i = 1; i <= maxd; i++)
  {
    if (Count.at(i) == 0)
    {
      cout << 0 << endl;
      return 0;
    }

    int64_t p = 1;
    for (int64_t j = 0; j < Count.at(i); j++)
      p = (p * Count.at(i - 1)) % MOD;
    ans = (ans * p) % MOD;
  }
  cout << (ans % MOD) << endl;
}


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

static const int NIL = -1;

struct Node {
	int parent;
	int left;
	int right;
	Node(int parent = NIL, int left = NIL, int right = NIL): parent(parent), left(left), right(right) {}
};

vector<Node> T;
vector<int> D;

void setDepth(int u, int depth)
{
	D[u] = depth;
	if (T[u].right != NIL) setDepth(T[u].right, depth);
	if (T[u].left != NIL) setDepth(T[u].left, depth + 1);
}

void print(int u)
{
	stringstream res;
	string type;
	if (T[u].parent == NIL) type = "root";
	else if (T[u].left == NIL) type = "leaf";
	else type = "internal node";
	
	res << "node " << u << ": ";
	res << "parent = " << T[u].parent << ", ";
	res << "depth = " << D[u] << ", ";
	res << type << ", [";
	
	bool f = false;
	for (int v = T[u].left; v != NIL; v = T[v].right){
		if (f) res << ", ";
		res << v;
		f = true;
	}
	res << "]";
	
	cout << res.str() << endl;
}

int main()
{
	int n;
	scanf("%d", &n);
	T.resize(n);
	D.resize(n);
	
	for (int i = 0; i < n; i++){
		int id, k;
		scanf("%d %d", &id, &k);
		
		int l = NIL;
		for (int j = 0; j < k; j++){
			int c;
			scanf("%d", &c);
			if (l == NIL) T[id].left = c;
			else T[l].right = c;
			l = c;
			T[c].parent = id;
		}
	}
	
	int root;
	for (int i = 0; i < n; i++){
		if (T[i].parent == NIL){
			root = i;
		}
	}
	
	setDepth(root, 0);
	
	for (int i = 0; i < n; i++){
		print(i);
	}
	
	return 0;
}

Measured memory_bytes: 7316
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int oo=1e9;
int num,vet[400005],val[400005],nex[400005],head[100005];
bool flag,vis[100005];
int f[100005];
inline int read()
{
	char ch=getchar(),la;
	while (ch<'0' || ch>'9') la=ch,ch=getchar();
	int ans=0;
	while (ch<='9' && ch>='0')
	{
		ans=ans*10+ch-48;
		ch=getchar();
	}
	if (la=='-') ans=-ans;
	return ans;
}
void write(int x)
{
	if (x<0)
	{
		printf("-");
		x=-x;
	}
	if (x>9) write(x/10);
	putchar(x%10+48);
}
void add(int u,int v,int l)
{
	num++;
	vet[num]=v;
	val[num]=l;
	nex[num]=head[u];
	head[u]=num;
}
void dfs(int u,int s)
{
	vis[u]=1;
	if (!flag) return;
	for (int i=head[u]; i; i=nex[i])
	{
		int v=vet[i];
		if (vis[v])
		{
			if (s+val[i]!=f[v]) 
			{
				flag=0;
				return;
			}
			continue;
		}
		f[v]=s+val[i];
		if (abs(f[v])>oo) 
		{
			flag=0;
			return;
		}
		dfs(v,s+val[i]);
	}
}
int main()
{
	int n=read(),m=read();
	if (m==0)
	{
		puts("Yes");
		return 0;
	}
	for (int i=1; i<=m; i++) 
	{
		int u=read(),v=read(),l=read();
		add(u,v,l); add(v,u,-l);
	}
	flag=1;
	for (int i=1; i<=n; i++)
	{
		if (!vis[i]) dfs(i,0);
		if (!flag) 
		{
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}

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

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

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

#define endl '\n'
#define PB push_back
#define PF push_front
#define MP make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

const int INF = 1e9 + 7;
const ll LINF = 1e18 + 14;

int main(){
    ios_base::sync_with_stdio(false); //cin.tie(nullptr); cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int sum = 0;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i-1]) sum++;
    }
    cout << min(n-1, sum + 2 * k);
    return 0;
} 


Measured memory_bytes: 512
#include <stdio.h>

#define min(x, y) ((x) > (y) ? (y) : (x))

int main(){
  int q1, b, c1, c2, q2, i, j, x, y;
  while(scanf("%d", &q1) && q1){
    scanf("%d%d%d%d", &b, &c1, &c2, &q2);
    y = 0;
    x = min(b / c1, q2);
    if(c2 * (q1 - 1) + c1 > b) x = y = -1;
    while(q1 > x + y || x * c1 + y * c2 > b || x > q2){
      if(x == -1 && y == -1) break;
      y++;
      if(x * c1 + y * c2 > b && x > 1) x--;
    }
    if(x + y < q1 || x < 1) x = -1;
    if(x == -1 || y == -1) puts("NA");
    else printf("%d %d\n", x, y + (b - x * c1 - y * c2) / c2);
  }
  return 0;
}

Measured memory_bytes: 612
//i??\??????i * P??????????????????????????????????????´????????????????°????????????????????§£?????????????????????????????????????????£??¨??????????????§????????????????§£?????????
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int n, p, q;
int c[500000];
int rc[500001];

signed main() {
	int i;
	
	cin >> n >> p >> q;
	for (i = 0; i < n; i++) { cin >> c[i]; c[i] += i * p; }
	
	sort(c, c + n);
	for (i = 1; i <= n; i++) { rc[i] = rc[i - 1] + c[i - 1]; }
	
	int ans = -1e+18;
	for (i = 0; i <= n; i++) {
		int jisui = i * p * q + 2 * p * i * (i - 1) / 2;
		int syoku = rc[n] - rc[i];
		ans = max(ans, jisui + syoku);
	}
	ans -= p * n * (n - 1) / 2;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 10976
from scipy.sparse import *
from itertools import *
 
n,m,r = [int(x) for x in input().split()]
R = [int(i)-1 for i in input().split()]
route_list = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  route_list[a-1][b-1] = c
  route_list[b-1][a-1] = c
 
Co = csgraph.floyd_warshall(route_list)
 
for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

Measured memory_bytes: 18956
def main():
    N, K = map(int, input().split())
    R, S, P = map(int, input().split())
    T = input()

    score = 0
    scores = {
        'r': P,
        's': R,
        'p': S
    }

    for i in range(K):
        prev = ''
        for j in range(N//K+1):
            idx = j*K+i
            if idx >= N:
                break
            current = T[idx]
            if current != prev:
                score += scores[current]
                prev = current
            else:
                prev = ''

    print(score)


if __name__ == '__main__':
    main()


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

int main(){
  int a,b;
  string s;
  cin >>a >>b >>s;
  bool can = true;
  for(int i = 0; i<a; i++){
    if(!('0'<=s[i]&&s[i]<='9')) can = false;
  }
  if(s[a]!='-') can = false;
  for(int i = a+1; i<=a+b; i++){
    if(!('0'<=s[i]&&s[i]<='9')) can = false;
  }
  if(can) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

#define                           int                         long long
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<int,int>
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);




using namespace std;

const int inf=1e18;
const int mod=1e9+7;
const int M=100009;

inline int bigmod(int B,int P){int R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}
inline int ad(int x,int y){int ret=(x%mod+y%mod)%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
inline int sub(int x,int y){int ret=((x%mod)-(y%mod)+mod)%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
inline int gun(int x,int y){int ret=((x%mod)*(y%mod))%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}


 main()

{
    fast
    int n,x;
    cin>>n>>x;
    int a[n+5];
    f(i,1,n)cin>>a[i];
    sort(a+1,a+n+1);
    int ses=0;
    f(i,1,n)
    {
        int nd=a[i];
        if(i==n)
        {
            if(nd==x)ses++;
        }
        else
        {
            if(nd<=x)
            {
                x=x-nd;
                ses++;
            }
        }
    }
    cout<<ses<<endl;
    return 0;

}





































Measured memory_bytes: 3652
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

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

def input_list_str():
  return list(map(str, input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
  w, h, x, y = input_list()
  way = 0
  if w == 2*x and h == 2*y:
    way = 1
  print((w*h)/2, way)
  
import math
import fractions
import collections
import itertools
from functools import reduce
main()

Measured memory_bytes: 5048
#include<bits/stdc++.h>
using namespace std;
#define int long long
main(){
    int n,k;
    cin>>n>>k;
    int h[200010];
    for(int i=1;i<=n;++i){
        cin>>h[i];
    }
    sort(h+1,h+n+1);
    int sum=0;
    for(int i=1;i<=n-k;++i){
        sum+=h[i];
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 1792
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def main():
    n = int(input())
    x = n * 800
    y = (n // 15) * 200
    print(x - y)


if __name__ == '__main__':
    main()

Measured memory_bytes: 2940
h, w = map(int, input().split())
S = [input() for _ in range(h)]

for i in range(h):
    for j in range(w):
        #print(S[i][j])
        cnt = 0
        if i == 0 or i == h - 1:
            cnt += 1
        if j == 0 or j == w - 1:
            cnt += 1

        if S[i][j] == "#" and i+1 < h and S[i+1][j] != "#":
                cnt += 1

        if S[i][j] == "#" and j+1 < w and S[i][j+1] != "#":
                cnt += 1

        if S[i][j] == "#" and i-1 > 0 and S[i-1][j] != "#":
                cnt += 1

        if S[i][j] == "#" and j-1 > 0 and S[i][j-1] != "#":
                cnt += 1

        if cnt == 4:
            print("No")
            exit()
print("Yes")

Measured memory_bytes: 9168
using System;
using System.Collections.Generic;

namespace AOJ
{
    class RightTriangle
    {
        public static void Main()
        {
            int len = int.Parse(Console.ReadLine().Trim());
            for (int i = 0; i < len; i++)
            {
                var input = Console.ReadLine().Trim().Split(' ');
                var test = new List<int>();
                test.Add((int)Math.Pow(int.Parse(input[0]), 2));
                test.Add((int)Math.Pow(int.Parse(input[1]), 2));
                test.Add((int)Math.Pow(int.Parse(input[2]), 2));
                test.Sort();
                if (test[0] + test[1] == test[2]) { Console.WriteLine("YES"); }
                else { Console.WriteLine("NO"); }
            }
        }
    }
}

Measured memory_bytes: 5600
# Author: cr4zjh0bp
# Created: Tue Mar 10 15:45:44 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N, M = na()
ab = nan(M)

G = [[] for _ in range(N)]
for i in range(M):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

def dfs(i, j, p):
    if j > 2:
        return False
    if i == N - 1 and j == 2:
        return True
    flag = False
    for k in range(len(G[i])):
        if G[i][k] == p:
            continue
        if dfs(G[i][k], j + 1, i):
            flag = True
    return flag

print("POSSIBLE" if dfs(0, 0, -1) else "IMPOSSIBLE")

Measured memory_bytes: 79512
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<functional>
#include<map>
using namespace std;
typedef long long ll;
int s(int n)
{
	int sum = 0, i, j, k, ge = 0, shi = 0, bai = 0, qian = 0;
	if (n == 10000)return 1;
	qian = n / 1000;
	bai = n / 100 % 10;
	ge = n % 10;
	shi = n % 100 / 10;
	return sum = ge + shi + bai + qian;
}
int main()
{
	int n, a, b; int su = 0;
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++)
		if (s(i) >= a&&s(i) <= b)su += i;
	cout << su << endl;
	//system("pause");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
    double max=0,min=0,h;
    int c=0;
    while(scanf("%lf",&h) != EOF){
        if(c==0) min = h;
        c++;
        if(max < h){
            max = h;
        }else if(min > h){
            min = h;
        }
    }
	printf("%f\n" ,max-min);
	return 0;
}

Measured memory_bytes: 648
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
        int P[] = new int[N];
        for(int i = 0; i < N; ++i){
            P[i] = sc.nextInt();
        }
        int count = 0;
        for(int i = 0; i < N-2; ++i){
            if(P[i] < P[i+1] && P[i+1] < P[i+2] || P[i] > P[i+1] && P[i+1] > P[i+2]){
             count += 1;   
            }
        }
        System.out.println(count);
	}
}

Measured memory_bytes: 35564
N = int(input())
A = list(map(int,input().split()))
from collections import Counter
def fac(n):
    return (n*(n-1))/2

cnt = Counter(A)

total = 0
for k,v in cnt.items():
    total += fac(cnt[k])

for a in A:
    print(int(total + fac(cnt[a]-1) - fac(cnt[a])))

Measured memory_bytes: 26140
n = int(input())
A = []
B = []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A.reverse()
B.reverse()
c = 0
for i in range(n):
    A[i] += c
    if A[i] % B[i] != 0:
        c += (B[i] - A[i] % B[i])
        A[i] += c
print(c)


Measured memory_bytes: 15016
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define MAX 100005

using namespace std;
typedef unsigned long long ull;

int n, a, ans[MAX];

int main(){
  cin >> n;
  rep(i, n){
    cin >> a;
    ans[a-1]=i+1;
  }
  rep(i, n){
    cout << ans[i] << " ";
  }
  return 0;
}


Measured memory_bytes: 1152
#include <stdio.h>

int main(void)
{
	int n, pm, pe, pj;
	int i;

	while (1) {
		scanf("%d", &n);
		if (n == 0)
			break;
		for (i = 0; i < n; i++) {
			scanf("%d%d%d", &pm, &pe, &pj);
			if (pm == 100 || pe == 100 || pj == 100 || pm + pe >= 180 || pm + pe + pj >= 240 )
				puts("A");
			else if (pm + pe + pj >= 210 || (pm + pe + pj >= 150 && pm >= 80 || pe >= 80))
				puts("B");
			else
				puts("C");
		}
	}
	return 0;
}

Measured memory_bytes: 584
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007


int main() {

  int N,M;
  cin >> N >> M;

  int c = 0,pe = 0;
  vector<int> wa(N,0);
  vector<bool> ac(N,true);
  for(int i = 0;i < M;i++) {
    int p;
    string S;
    cin >> p >> S;
    p--;
    if(S == "AC") {
      if(ac.at(p)) {
        c++;
        ac.at(p) = false;
      }
    }else {
      if(ac.at(p)) wa.at(p)++;
    }
  }
  
  for(int i = 0;i < N;i++) {
    if(!ac.at(i)) pe += wa.at(i);
  }

  cout << c << " " << pe << endl;
}


Measured memory_bytes: 640
# ハフマン符号
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/15/ALDS1_15_D

from collections import Counter
import heapq


class Node:
    def __init__(self, count, val=None, left=None, right=None):
        self.val = val
        self.count = count
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.count < other.count


class HuffmanCoding:
    def __init__(self, s: str):
        self.s = s
        self.counts = Counter(s).most_common()
        self.root = self.build_tree()
        self.encode_table = self.gen_encode_table()

    def build_tree(self):
        hq = list()
        for val, cnt in self.counts:
            heapq.heappush(hq, Node(cnt, val))
        while len(hq) > 1:
            x = heapq.heappop(hq)
            y = heapq.heappop(hq)
            cnt = x.count + y.count
            z = Node(cnt, None, y, x)
            heapq.heappush(hq, z)
        if hq:
            return heapq.heappop(hq)
        else:
            return None

    def gen_encode_table(self):
        encode_table = {}

        def traversal(node, key):
            if node.val:
                if key == "":
                    key = "0"
                encode_table[node.val] = key
            else:
                if node.left:
                    traversal(node.left, key + "1")
                if node.right:
                    traversal(node.right, key + "0")
        key = ""
        if self.root:
            traversal(self.root, key)

        return encode_table

    def get_encode_size(self):
        size = 0
        for a in self.s:
            size += len(self.encode_table[a])
        return size

    def gen_encode_bin(self):
        enc = ""
        for a in self.s:
            enc += self.encode_table[a]
        return enc


def main():
    S = input().strip()
    huffman = HuffmanCoding(S)
    print(huffman.get_encode_size())


if __name__ == "__main__":
    main()



Measured memory_bytes: 6188
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    char s[100001];
    scanf("%s", s);
    int cnts[100000];
    cnts[0] = 0;
    bool wasA = s[0] == 'A';
    for (int i = 1; i < n; i++)
    {
        if (wasA && s[i] == 'C')
        {
            cnts[i] = cnts[i - 1] + 1;
        }
        else
        {
            cnts[i] = cnts[i - 1];
        }

        wasA = s[i] == 'A';
    }

    for (int i = 0; i < q; i++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", cnts[r - 1] - cnts[l - 1]);
    }
}

Measured memory_bytes: 1280
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<algorithm>
#include<functional>
#define ll long long
#define inf  999999999
#define pa pair<int,int>
using namespace std;


int main(){
int c[22],n,m;
cin>>n>>m;
for(int i=0;i<m;i++) cin>>c[i];
static int dp[22][50010];
for(int i=0;i<m+1;i++){
for(int j=0;j<n+1;j++) dp[i][j]=inf;
dp[i][0]=0;
}

for(int i=0;i<m;i++){
for(int j=0;j<c[i];j++) dp[i+1][j]=dp[i][j];
for(int j=c[i];j<n+1;j++){
dp[i+1][j]=min(dp[i+1][j-c[i]]+1,dp[i][j]);
}
}

cout<<dp[m][n]<<endl;

return 0;
}

Measured memory_bytes: 5260