akhauriyash/Code-Regression huggingface dataset:
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int maxn = (int) 1e5 + 5;
int n, m;
vector<pair<int, int>> g[maxn];

bool read() {
  if (scanf("%d%d", &n, &m) < 2) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < m; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    v--;
    u--;
    g[v].push_back(make_pair(u, 1));
    g[u].push_back(make_pair(v, 2));
  }
  return true;
}

int col[maxn];
int cnt[3];
int es;

bool dfs(int v, int c) {
  col[v] = c;
  cnt[c]++;
  es += sz(g[v]);
  bool ok = true;
  for (int i = 0; i < sz(g[v]); i++) {
    int u = g[v][i].first, w = g[v][i].second;
    int nc = (c + w) % 3;
    if (col[u] != -1) {
      if (col[u] != nc) {
        ok = false;
      }
      continue;
    }
    if (!dfs(u, nc)) {
      ok = false;
    }
  }
  return ok;
}

void solve() {
  for (int i = 0; i < n; i++) {
    col[i] = -1;
  }
  long long res = 0;
  for (int i = 0; i < n; i++) {
    if (col[i] != -1) {
      continue;
    }
    for (int j = 0; j < 3; j++) {
      cnt[j] = 0;
    }
    es = 0;
    if (dfs(i, 0)) {
      if (!cnt[0] || !cnt[1] || !cnt[2]) {
        assert(!(es & 1));
        res += es / 2;
      } else {
        for (int j = 0; j < 3; j++) {
          res += (long long) cnt[j] * cnt[(j + 1) % 3];
        }
      }
    } else {
      int vs = cnt[0] + cnt[1] + cnt[2];
      res += (long long) vs * vs;
    }
  }
  printf("%lld\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


Measured memory_bytes: 12416
//jinhaonan
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
template<class T>inline void read(T &x){
	x=0;char c=getchar();bool f=0;
	for(;c>'9'||c<'0';f=c=='-',c=getchar());
	for(;c>='0'&&c<='9';x=(x<<1)+(x<<3)+c-'0',c=getchar());
	x=f?-x:x;
}
template<class T>inline void write(T x){
	if(x<0)putchar('-'),x=-x;
	if(x>=10)write(x/10);
	putchar(x%10+48);
}
template<class T>inline bool chkmax(T &a,T const &b){
	return a<b?a=b,1:0;
}
template<class T>inline bool chkmin(T &a,T const &b){
	return a>b?a=b,1:0;
}
int main(){
	int n,k;read(n),read(k);
	int d=n/k;
	long long ans=(long long)d*d*d;
	if(!(k&1)){
		if(n%k>=(k/2))
			++d;
		ans+=(long long)d*d*d;
	}
	write(ans),putchar('\n');
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
int main(){
    int n;
    cin >> n;
    int male = 0;
    int famale = 0;
    rep(i, n){
        string s, t;
        cin >> s >> t;
        if (s > t) male += 3;
        if (s == t){
          male++; famale++;
        }
        if (t > s) famale += 3;
    }
    cout << male << " " << famale << endl;
}


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

#define fr(i,n) _back
#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int T = 2e3+3;
ll dp[T][T];
vii v;

int main() {
    ios_base::sync_with_stdio(false);
    int n; cin >> n;

    for(int i = 0; i < n; i++) {
        int x; cin >> x;
        v.eb(x,i+1);
    }

    sort(v.begin(),v.end());

    ll ans = 0;
    for(int i = n-1; i >= 0; i--)
        for(int j = 1; j+i <= n; j++) {
            dp[j+1][j+i] = max(dp[j+1][j+i], dp[j][j+i]+abs(v[i].se-j)*v[i].fi);
            dp[j][j+i-1] = max(dp[j][j+i-1], dp[j][j+i]+abs(v[i].se-(j+i))*v[i].fi);
            ans = max({ans,dp[j+1][j+i],dp[j][j+i-1]});
        }

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



Measured memory_bytes: 26360
#include <stdio.h>
#include<cmath>
using namespace std;

int main(){
	double x1,x2,x3,x4,y1,y2,y3,y4;
	int n;
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4);

		if(abs((y2 - y1)*(x4 - x3) - (y4 - y3)*(x2 - x1) ) < 0.0000000001){ //I copied yutaka watabe's code here
			printf("YES\n");
		}else{
			printf("NO\n");
		}

	}
    return 0;
}

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

using namespace std;
#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

const int inf = 1e9+7;
const int mod = 1e9+7;

int main(){
    ll k,a,b;
    cin>>k>>a>>b;

    ll have=1;

    if(b-a<=2) have+=k;

    else {
        k-=a-1;
        have+=a-1;

        have+=k/2*(b-a);
        if(k%2) have++;
    }

    cout<<have<<endl;

}


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

using LLI = long long int;

int N;
LLI T;
LLI ts[11451419];
LLI ans;
LLI until, from;

int main() {
  scanf("%d%lld", &N, &T);
  for (int i=0; i<N; i++) {
    scanf("%lld", &ts[i]);
    if (until < ts[i]) {
      ans += until-from;
      from = ts[i];
      until = ts[i]+T;
    } else {
      until = ts[i]+T;
    }
  }
  
  printf("%lld\n", ans+until-from);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
using namespace std;
  
int main () {
  int n;
  cin >> n;
  for(int i=1;i<10;i++) {
    for(int j=1;j<10;j++) {
      if(n == i * j) {
        cout << "Yes";
        return 0;
      }
    }
  }
  cout << "No";     
}

Measured memory_bytes: 256
class uf():


    def __init__(self,n):
        self.size=n
        self.parents=list(range(n))


    def find(self,x):
        if self.parents[x]==x:
            return x
        self.parents[x]=self.find(self.parents[x])
        return self.find(self.parents[x])


    def union(self,a,b):
        x=self.find(a)
        y=self.find(b)
        if x==y:
            return
        if x>y:
            x,y=y,x
        self.parents[y]=x


n,m=map(int,input().split())
fri=uf(n)
for c in range(m):
    a,b=map(int,input().split())
    fri.union(a-1,b-1)
l=[0]*n
for c in range(n):
    l[fri.find(c)]+=1
print(max(l))

Measured memory_bytes: 18284
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
 
using namespace std;
                        
template<typename T> void uin(T &a, T b) {
    if (b < a) {
        a = b;
    }
}
                        
template<typename T> void uax(T &a, T b) {
    if (b > a) {
        a = b;
    }
}

#define int long long
#define ghost signed
#define left left228
#define right right228
#define complex complex228
#define count count228
#define sin sin228
#define list list228

const int N = 505;

int a[N];

vector<int> get_divisors(int n) {
	int i = 1;
	vector<int> divisors;
	while (i * i <= n) {
		if (n % i == 0) {
			divisors.push_back(i);
			if (i * i != n) divisors.push_back(n / i);
		}
		++i;
	}
	return divisors;
}

ghost main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	int n, k;
	cin >> n >> k;
	int sum = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		sum += a[i];
	}
	vector<int> desu = get_divisors(sum);
	int res = 1;
	for (int d : desu) {
		vector< pair<int, int> > v;
		int S = 0;
		for (int i = 1; i <= n; ++i) {
			if (a[i] % d) {
				v.emplace_back(a[i] % d, d - a[i] % d);
				S += v.back().first;
			}
		}
		sort(v.rbegin(), v.rend());
		bool OK = 0;
		int T = 0;
		for (int cnt = 1; cnt <= (int)v.size(); ++cnt) {
			T += v[cnt - 1].first;
			int cur = max(S - T, d * cnt - T);
			if (cur <= k) {
				OK = 1;
				break;
			}
		}
		if (OK) uax(res, d);
	}
	cout << res << '\n';
    return 0;
} // kek ;
// Ого! Кажетсья это $#@!
 
 
 
 


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define vl vector<ll>
#define pl pair<ll,ll>
#define mp make_pair
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) for(ll i=0;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(),(v).end()
using namespace std;
ll x,y;
ll solve(ll a,ll ans) {
    if(a>y)return ans;
    solve(a*2,ans+1);
}
signed main() {
    cin>>x>>y;
    cout<<solve(x,0)<<endl;
}


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

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

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

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

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


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

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

main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    int x;
    for (int i = 0; i < m; i++) {
        cin >> x;
        n -= x;
    }
    if (n < 0) {
        cout << "-1\n";
    }
    else {
        cout << n << '\n';
    }
}


Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <bitset>
#include <time.h>
#include <set>
#include <algorithm>
#define MAXN 200010
#define ll long long
using namespace std;

// a(l)+...a(r) >= K*(r-l+1)
// (a(l)-K)+...+(a(r)-K) >= 0

ll tree[MAXN+2];

ll read(int idx){
    ll sum = 0;
    while (idx > 0){
        sum += tree[idx];
        idx -= (idx & -idx);
    }
    return sum;
}

void update(int idx ,int val){
    while (idx <= MAXN){
        tree[idx] += val;
        idx += (idx & -idx);
    }
}

ll A[MAXN+2];


int main() {
    int N,K;
    cin>>N>>K;
    for(int i=1;i<=N;i++)
        cin>>A[i];
    
    
    for(int i=1;i<=N;i++)
        A[i] -= K;
    
    
    vector<ll> all_sumalls;
    all_sumalls.push_back(0);
    
    ll sumall = 0;
    for(int i=1;i<=N;i++) {
        sumall += A[i];
        all_sumalls.push_back(sumall);
    }
    
    set<ll> all_sumalls_set(all_sumalls.begin(), all_sumalls.end());
    
    
    map<ll,int> mapping;
    for(ll x : all_sumalls_set) {
        int sz = mapping.size();
        mapping[x] = sz+1;
    }
    
    
    
    for(int j=0;j<all_sumalls.size();j++) {
        all_sumalls[j] = mapping[all_sumalls[j]];
    }
    
    
    for(int i=1;i<=MAXN;i++)
        tree[i]=0;
    
    ll ans = 0;
    for(int i=0;i<all_sumalls.size();i++) {
        ans += read(all_sumalls[i]);
        update(all_sumalls[i],1);
    }
    
    cout << ans << endl;
    
    
    
    
    
    
    
    
}

Measured memory_bytes: 26864
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int N;
  cin >> N;
  vector<int> P(N);
  rep(i,N) cin >> P[i];
  int ans = 0;
  int t = 99999999;
  rep(i,N) {
    if (P[i] <= t) {
      t = P[i];
      ++ans;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3560
from operator import itemgetter
n=int(input())
xl=[list(map(int,input().split()))for i in range(n)]
R=[(xl[i][0]-xl[i][1],xl[i][0]+xl[i][1]) for i in range(n)]
r=sorted([(R[i][0],R[i][1]) for i in range(n)],key=itemgetter(1))
s=r[0][1]
ans=1
for i in range(n-1):
    if r[i+1][0]>=s:
        s=r[i+1][1]
        ans+=1
print(ans)

Measured memory_bytes: 50728
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

int gcd(int,int);
  
int main(){

  int x,y,d;
  scanf("%d%d",&x,&y);
  d = gcd(x,y);
  printf("%d\n",d);
  return 0;
}

int gcd(int x,int y){
  int r,temp;
  if (x < y){
    temp = y;
  y = x;
  x = temp;
  }
  while (y > 0){
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}



Measured memory_bytes: 2144
import java.util.*;
public class Main{
  public static void main (String args[]){
    Scanner sc = new Scanner(System.in);
    
    int ans = 0;
    
    for (int i = 0; i < 5; i++){
      int a = sc.nextInt();
      if (a==0){
        ans = i + 1;
        break;
      }
    }
    
    System.out.println(ans);
  }
}

Measured memory_bytes: 35652
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <sstream>

#define ll long long int
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()
#define INF 100000000
using namespace std;

int main(){
	int N;
	cin >> N;
	bool s[N];//true = white
	int min=INF;
	rep(i,0,N){
		char tmp;
		cin >> tmp;
		if(tmp == '.'){
			s[i] = true;
		}else{
			s[i] = false;
		}
	}
	int count=0;
	rep(i,0,N){
		if(s[i] == true){
			count++;
		}
	}
	min = count;

	rep(i,0,N){
		if(s[i] == true){
			count--;
		}else{
			count++;
		}
		if(min>count){
			min = count;
		}
	}

	cout << min << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int H,N;
int A[100010];

signed main(){
	cin>>H>>N;
	int sum=0;
	REP(i,N){
		cin>>A[i];
		sum+=A[i];
	}
	if(sum>=H){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<string.h>
#include<limits.h>
#define CMAX 26
#define SMAX 100
#define MIN(a,b) ((a) < (b) ? (a) : (b))

int net[CMAX][CMAX], matrix[CMAX+2][CMAX+2], iter[CMAX+2], level[CMAX+2];
int Bfs(int, int, int);
int Dfs(int, int, int, int);
int main(void)
{
  int i, j, k, n, v;
  char buf[SMAX];
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    int len, a, b;
    scanf("%s%*c", buf);
    len = strlen(buf);
    a = buf[0] - 'a';
    b = buf[len-1] - 'a';
    net[a][b]++;
  }
  for (i = 0; i < CMAX; i++) {
    int maxflow = 0, inflow = 0, outflow = 0;
    for (j = 0; j < CMAX; j++) {
      inflow += net[j][i];
      outflow += net[i][j];
    }
    v = CMAX + 2;
    memset(matrix, 0, sizeof(matrix));
    for (j = 0; j < CMAX; j++) {
      for (k = 0; k < CMAX; k++) {
        if (j == i && k == i) matrix[CMAX][CMAX+1] = net[i][i];
        else if (j == i && k != i) matrix[CMAX][k] = net[i][k];
        else if (j != i && k == i) matrix[j][CMAX+1] = net[j][i];
        else matrix[j][k] = net[j][k];
      }
    }
    while (Bfs(CMAX, CMAX + 1, v)) {
      memset(iter, 0, sizeof(iter));
      maxflow += Dfs(CMAX, CMAX + 1, v, INT_MAX);
    }
    if (outflow == maxflow && inflow > 0) printf("%c\n", i + 'a');
  }
}

int Bfs(int s, int t, int size)
{
  int i, v, head = 0, tail = 0, queue[CMAX+2];
  memset(level, -1, sizeof(level));
  level[s] = 0;
  queue[tail++] = s;
  do {
    i = queue[head++];
    for (v = 0; v < size; v++) {
      if (level[v] < 0 && matrix[i][v] > 0) {
        queue[tail++] = v;
        level[v] = level[i] + 1;
      }
    }
  } while (head != tail);
  return level[t] >= 0;
}

int Dfs(int u, int t, int size, int f)
{
  int *i, fsum = 0;
  if (u == t) return f;
  for (i = &iter[u]; *i < size; (*i)++) {
    if (level[u] < level[(*i)] && matrix[u][(*i)] > 0) {
      int ftemp = Dfs((*i), t, size, MIN(f - fsum, matrix[u][(*i)]));
      if (ftemp > 0) {
        matrix[u][(*i)] -= ftemp;
        matrix[(*i)][u] += ftemp;
        fsum += ftemp;
        if (fsum == f) break;
      }
    }
  }
  return fsum;
}


Measured memory_bytes: 2056
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
logk = N.bit_length()

# 漸化式にできるなら行列計算に落とし込める
# A[n] = A[n - 1] + A[n - 3]なので
# [a2, a1, a0] = [0, 0, 1]
# [[1, 1, 0], [0, 0, 1], [1, 0, 0]]のN乗をすれば
# [an+2, an+1, an] が出る

dp = [[[0, 0, 0] for i in range(3)] for i in range(logk)]
dp[0] = [
[1, 1, 0],
[0, 0, 1],
[1, 0, 0]
]

# 行列掛け算 O(n3)かかる
def array_cnt(ar1, ar2):
    h = len(ar1)
    w = len(ar2[0])
    row = ar1
    col = []
    for j in range(w):
        opt = []
        for i in range(len(ar2)):
            opt.append(ar2[i][j])
        col.append(opt)

    res = [[[0, 0] for i in range(w)] for i in range(h)]
    for i in range(h):
        for j in range(w):
            cnt = 0
            for x, y in zip(row[i], col[j]):
                cnt += x * y
            res[i][j] = cnt
            res[i][j] %= mod
    return res

for i in range(1, logk):
    dp[i] = array_cnt(dp[i - 1], dp[i - 1])

ans = [[0, 0, 1]]
for i in range(logk):
    if N & (1 << i):
        ans = array_cnt(ans, dp[i])
print(ans[0][2] % mod)

Measured memory_bytes: 83224
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int gcd(int a, int b)
{
	while (b) {
		int t = a % b;
		a = b;
		b = t;
	}
	return a;
}

int N, A[2020];
vector<int> dv[2020];
vector<int> rdiv[50505];
int RC;

bool isok[2020], used[2020];
bool rdivvis[50505];
bool vis[2020];

int chk()
{
	for (int i = 0; i < N; ++i) vis[i] = false;
	for (int i = 0; i < RC; ++i) rdivvis[i] = false;

	queue<int> Qa;
	int top = 0;
	int ret = -1;

	for (;;) {
		while (top < N) {
			if (!used[top] && isok[top] && !vis[top]) {
				Qa.push(top);
				vis[top] = true;
				ret = top;
				break;
			}
			++top;
		}
		if (top == N) break;
		while (!Qa.empty()) {
			int v = Qa.front(); Qa.pop();
			for (int p : dv[v]) if (!rdivvis[p]) {
				rdivvis[p] = true;
				for (int i : rdiv[p]) if (!used[i] && !vis[i]) {
					vis[i] = true;
					Qa.push(i);
				}
			}
		}
	}
	return ret;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", A + i);
	}
	sort(A, A + N);
	for (int i = 0; i < N; ++i) {
		int v = A[i];
		for (int j = 2; j * j <= v; ++j) {
			if (v % j == 0) {
				dv[i].push_back(j);
				while (v % j == 0) v /= j;
			}
		}
		if (v > 1) dv[i].push_back(v);
	}
	vector<int> alldv;
	for (int i = 0; i < N; ++i) {
		for (int p : dv[i]) alldv.push_back(p);
	}
	sort(alldv.begin(), alldv.end());
	alldv.erase(unique(alldv.begin(), alldv.end()), alldv.end());
	for (int i = 0; i < N; ++i) {
		for (int &p : dv[i]) {
			p = lower_bound(alldv.begin(), alldv.end(), p) - alldv.begin();
			rdiv[p].push_back(i);
		}
	}
	RC = alldv.size();

	for (int i = 0; i < N; ++i) {
		isok[i] = true;
		used[i] = false;
	}

	vector<int> ans;
	for (int i = 0; i < N; ++i) {
		int id = chk();
		int v = A[id];
		ans.push_back(v);
	//	printf("%d\n", v);
		used[id] = true;
		for (int j = 0; j < N; ++j) {
			if (A[j] > v) {
				isok[j] = false;
			}
			if (gcd(A[j], v) != 1) {
				isok[j] = true;
			}
		}
	}

	for (int i = 0; i < N; ++i) printf("%d%c", ans[i], i == N - 1 ? '\n' : ' ');

	return 0;
}


Measured memory_bytes: 1792
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef array<LL,50> A;
int N;
int a[50];
int b[50];
bool f(A s,int k)
{
	if(k==0){
		for(int i=0;i<N;i++){
			if(!(s[i]&(1LL<<b[i]))){
				return false;
			}
		}
		return true;
	}
	for(int i=0;i<N;i++){
		for(int j=50;j>=k;j--){
			if(s[i]&(1LL<<j)){
				s[i]|=(1LL<<(j%k));
			}
		}
	}
	return f(s,k-1);
}
LL g(A s,int k){
#if 0 
	assert(f(s,k));
	cerr << k << endl;
	for(int i=0;i<N;i++){
		cerr << s[i] << " ";
	}
	cerr << endl;
#endif
	if(k==0){
		return 0;
	}
	if(f(s,k-1)){
		return g(s,k-1);
	}
	for(int i=0;i<N;i++){
		for(int j=50;j>=k;j--){
			if(s[i]&(1LL<<j)){
				s[i]|=(1LL<<(j%k));
			}
		}
	}
	return (1LL<<k)+g(s,k-1);
}
int main() {
	cin >> N;
	A s={{}};
	for(int i=0;i<N;i++){
		cin >> a[i];
		s[i]=1LL<<a[i];
	}
	for(int i=0;i<N;i++){
		cin >> b[i];
	}
	if(!f(s,50)){
		cout << -1 << endl;
	}
	else{
		cout << g(s,50) << endl;
	}

	return 0;
}



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

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  double T, X;
  cin >> T >> X;
  cout << setprecision(20) << T / X << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main(){
    int n;
    cin >> n;
    vector<pair<ll,ll> > p(n),q(n);
    rep(i,n){
        cin >> p[i].first >> q[i].first;
        p[i].second = (ll)i;
        q[i].second = (ll)i;
    }
    sort(p.begin(),p.end(),greater<pair<ll,ll> >());
    sort(q.begin(),q.end()); 
    vector<bool>flag(n);
    ll t = 0;
    int x = 0;
    int y = 0;
    int cnt = 0;
    ll tmp = 0;
    bool r = 1;
    
        while(cnt < n){
            //cout << t << " " <<r <<endl;
            if(r){
                if(flag[p[x].second]){
                    x++;
                    continue;
                }
                if(t>p[x].first){
                    break;
                }
                tmp += abs(t-p[x].first);
                flag[p[x].second]=1;
                t = p[x].first;
                x++;
                cnt++;
                r=0;
            }else{
                if(flag[q[y].second]){
                    y++;
                    continue;
                }
                if(t<q[y].first){
                    break;
                }
                tmp += abs(t-q[y].first);
                flag[q[y].second]=1;
                t = q[y].first;
                y++;
                cnt++;
                r=1;
            }

        }
        tmp += abs(t);
    
    ll ans = tmp;
    vector<bool>flag2(n);
    t = 0;
    x = 0;
    y = 0;
    cnt = 0;
    tmp = 0;
    r = 0;
    
        while(cnt < n){
            //cout << t << " " <<r <<endl;
            if(r){
                if(flag2[p[x].second]){
                    x++;
                    continue;
                }
                if(t>p[x].first){
                    break;
                }
                tmp += abs(t-p[x].first);
                flag2[p[x].second]=1;
                t = p[x].first;
                x++;
                cnt++;
                r=0;
            }else{
                if(flag2[q[y].second]){
                    y++;
                    continue;
                }
                if(t<q[y].first){
                    break;
                }
                tmp += abs(t-q[y].first);
                flag2[q[y].second]=1;
                t = q[y].first;
                y++;
                cnt++;
                r=1;
            }

        }
        tmp += abs(t);
    
    cout << max(ans,tmp) << endl;
    return 0;
}

Measured memory_bytes: 3456
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int n = sc.nextInt();
        int tmp = sc.nextInt();
        int m = sc.nextInt();
        if(n == m){
          System.out.println(0);
        }else{
          System.out.println(1);
        }
    }
}

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

int main(){
  int x,a,b;
  cin>>x>>a>>b;

  char ans;
  if(abs(x-a)<abs(x-b)){
    ans='A';
  }else{
    ans='B';
  }
  cout<<ans;
  return 0;
}


Measured memory_bytes: 256
import heapq

N, M = map(int, input().split())
A = [-int(i) for i in input().split()]

heapq.heapify(A)

for _ in range(M):
    x = heapq.heappop(A) / 2
    heapq.heappush(A, x)

ans = 0
for a in A:
    ans -= int(a)

print(ans)


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

int N;

int main() {
	scanf("%d", &N);
	if(N % 10 == 3) puts("bon");
	else if(N % 10 == 0 || N % 10 == 1 || N % 10 == 6 || N % 10 == 8) puts("pon");
	else puts("hon");
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll i=1,j,k,n,a,c,b,r,p,cnt=0,s=1;
    cin>>n>>k;
    while(n>0)
    {
        n-=k;
        cnt++;
    }
    cout<<cnt<<endl;

    return 0;
}


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

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using ull = unsigned long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vc = vector<char>;
using vvc = vector<vc>;
using ii = pair<int,int>;
using vii = vector<ii>;
using vvii = vector<vii>;
using dd = pair<double, double>;
using vdd = vector<dd>;
using vvdd = vector<vdd>;
using Mii = map<int,int>;
using vMii = vector<Mii>;

#define fi first
#define se second
#define INF INT_MAX
#define mod(a,m) (a%m+m)%m
#define PB push_back
#define MP make_pair

vi value, weight;

vvll memo;

ll dp(int pas, int v) {
	int n = weight.size();
	if(v == 0) return 0;
	if(pas == n) return 1e15;
	ll& ans = memo[pas][v];
	if(ans != -1) return ans;
	ans = dp(pas + 1, v);
	if(value[pas] <= v) {
		ans = min(ans, weight[pas] + dp(pas + 1, v - value[pas]));
	}
	return ans;
}

int main(){
//	cout.setf(ios::fixed);
//	cout.precision(4);
	int n, w;
	while (cin >> n >> w) {
		weight = vi(n);
		value = vi(n);
		int max_val = 0;
		for (int i = 0; i < n; ++i) {
			cin >> weight[i] >> value[i];
			max_val += value[i];
		}
		memo = vvll(n, vll(max_val + 1, -1));
		int ans = 0;
		for (int i = max_val; i > 0 and not ans; --i) {
			if(dp(0, i) <= w) ans = i;
		}
		cout << ans << '\n';
	}
}




Measured memory_bytes: 79360
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static int[][] map;
	static int[][] directions8= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
	static int[][] directions4= {{-1,0},{1,0},{0,-1},{0,1}};
	static long ans;
	static int[] parent;//union-find用
	static int[] rank;//union-find用

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int P = sc.nextInt();

		String S = sc.next();

		//今までに出たMod値の数
		long [] modP = new long[P];

		ans = 0;

		if(P==2 || P==5) {
			for(int i = N-1;i>=0 ; i--){
				int n = Character.getNumericValue(S.charAt(i));
				if(n%P==0) {
					ans+=i+1;
				}
			}
		}else {
			int nowMod = 0;
			long cardinal = 1;

			for(int digit = N-1;digit>=0 ; digit--) {
				long n = Character.getNumericValue(S.charAt(digit))*cardinal;
				nowMod +=n % P;
				nowMod%=P;
				if(nowMod==0) {
					ans++;
				}
				ans+=modP[nowMod];
				modP[nowMod]++;
				cardinal*=10;
				cardinal%=P;
			}
		}

		System.out.println(ans);
	}

	//素数判定
	public static boolean isPrime(long num) {
		if (num < 2) return false;
		else if (num == 2) return true;
		else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

		double sqrtNum = Math.sqrt(num);
		for (int i = 3; i <= sqrtNum; i += 2)
		{
			if (num % i == 0)
			{
				// 素数ではない
				return false;
			}
		}

		// 素数である
		return true;
	}

	//BFS用に二つの配列を足し算する
	static int[] addArrayElms(int[] a, int[] b) {
		int[] c = new int[a.length];
		for(int i = 0; i < a.length; i++) {
			c[i] = a[i] + b[i];
		}
		return c;
	}

	//	//二分探索
	//k <= num となる最小の配列要素kのインデックスを返す
	static private int binarySearch(long num, long[] orderedArray){
		int lowerBorder = -1;
		int upperBorder = orderedArray.length;
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedArray[mid]<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//二分探索
	//k <= num となる最小のList要素kのインデックスを返す
	static private int binarySearch(long num, ArrayList<Long> orderedList){
		int lowerBorder = -1;
		int upperBorder = orderedList.size();
		int mid;

		while(upperBorder - lowerBorder >1) {
			mid = (upperBorder + lowerBorder)/2;
			if(orderedList.get(mid)<=num) {
				lowerBorder = mid;
			}else {
				upperBorder = mid;
			}
		}
		return lowerBorder;
	}

	//aとbの最小公倍数を求める
	public static int gcd(int a, int b) {
		return b == 0 ? a: gcd(b, a % b);
	}
	public static long gcd(long a, long b) {
		return b == 0 ? a: gcd(b, a % b);
	}

	//Union-Find用の配列を要素数nで初期化
	static void ufInit(int n){
		parent = new int[n];
		rank = new int[n];
	}

	//Union-Findの要素の最上位の親（グループ名）を返す
	static int ufFind(int a) {
		if(parent[a]==a) {
			return a;
		}else {
			return ufFind(parent[a]);
		}
	}

	//Union-Find木を連結する
	static void ufUnite(int a, int b) {
		a = parent[a];
		b = parent[b];

		if(a==b) {
			return;
		}
		if(rank[a] > rank[b]){
			parent[b]=a;
		}else {
			parent[a]=b;
			if(rank[a]==rank[b]) {
				rank[b]++;
			}
		}
	}

	static boolean ufSame(int a, int b) {
		return ufFind(a)==ufFind(b);
	}
}


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

// main.cpp

int main() {
  std::int_fast64_t n;
  std::cin >> n;
  std::array<std::vector<std::int_fast64_t>, 2> a;
  a[0].reserve(n);
  std::copy_n(std::istream_iterator<std::int_fast64_t>(std::cin), n, std::back_inserter(a[0]));
  a[1].reserve(n);
  std::copy_n(std::istream_iterator<std::int_fast64_t>(std::cin), n, std::back_inserter(a[1]));

  std::vector<std::int_fast64_t> row0(n);
  for (std::int_fast64_t i = 0; i < n; ++i) {
    row0[i] = (i > 0 ? row0[i - 1] : 0) + a[0][i];
  }
  std::vector<std::int_fast64_t> row1(n);
  for (std::int_fast64_t i = n - 1; i >= 0; --i) {
    row1[i] = (i < n - 1 ? row1[i + 1] : 0) + a[1][i];
  }

  std::int_fast64_t answer = 0;
  for (std::int_fast64_t i = 0; i < n; ++i) {
    answer = std::max(answer, row0[i] + row1[i]);
  }

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

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

int main(){
    ll n;
    cin >> n;
    ll ans=1;
    ll a=0,b=0,c=0;

    ll nn;
    ll mod=1e9+7;

    rep(i,n){
        cin >> nn;
        if(nn==a){
            ++a;
            if(nn==b and nn==c){
                ans*=3;
                ans=ans%mod;
            }
            else if(nn==b or nn==c){
                ans*=2;
                ans=ans%mod;
            }
        }
        else if(nn==b){
            ++b;
            if(nn==c){
                ans*=2;
                ans=ans%mod;
            }
        }
        else if(nn==c){
            ++c;
        }
        else{
            ans=0;
            break;
        }
    }

    cout << ans << endl;
    

    return 0;
}

Measured memory_bytes: 3676
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define MAX_V 400010
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
template<typename A, size_t NNN, typename T>
void Fill(A (&array)[NNN], const T &val){
    fill( (T*)array, (T*)(array+NNN), val );
}
#define INF 1e9+7
#define LLINF 1e18+7
ll MOD=1e9+7;
#define N 3000000
ll n,m,k;
ll a[N];
ll b[N];
ll dp[30][N];
int c[30][30];
int main(){
    n=in();
    dp[0][0]=1;
    rep(i,n)rep(j,n)c[i][j]=in();
    vec v[30];
    rep(i,1<<n){
        int t=i,res=0;
        while(t){
            res+=t%2;
            t/=2;
        }
        v[res].pb(i);
    }
    rep(i,n){
        rep(j,n){
            if(c[i][j])
            for(auto k:v[i]){
                dp[i+1][k|(1<<j)]=(dp[i+1][k|(1<<j)]+dp[i][k])%MOD;
            }
        }
    }
    cout<<dp[n][(1<<n)-1];
    return 0;
}

Measured memory_bytes: 357820
N,M= map(int,(input().split()))
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

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
a = prime_factorize(N)
b = prime_factorize(M)
c= set(a) & set(b)
print(len(c)+1)
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

Measured memory_bytes: 9048
#include <bits/stdc++.h>
using namespace std;
template <int64_t N>
class modint {
    int64_t x;

public:
    modint(int64_t x = 0) : x((x % N + N) % N) {}
    modint operator-() const { return modint(-x); }
    modint& operator+=(const modint& a) {
        if ((x += a.x) >= N) x -= N;
        return *this;
    }
    modint& operator-=(const modint& a) {
        if ((x += N - a.x) >= N) x -= N;
        return *this;
    }
    modint& operator*=(const modint& a) {
        (x *= a.x) %= N;
        return *this;
    }
    modint operator+(const modint& a) const {
        return modint(*this) += a;
    }
    modint operator-(const modint& a) const {
        return modint(*this) -= a;
    }
    modint operator*(const modint& a) const {
        return modint(*this) *= a;
    }
    modint pow(int64_t t) const {
        if (not t) return 1;
        modint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    // for prime mod
    modint inv() const { return pow(N - 2); }
    modint& operator/=(const modint& a) {
        return (*this) *= a.inv();
    }
    modint operator/(const modint& a) const {
        return modint(*this) /= a;
    }
    friend ostream& operator<<(ostream& os,
                               const modint& m) {
        os << m.x;
        return os;
    }
};

const int64_t mod = 1e9 + 7;
using mint = modint<mod>;

int main() {
    int s;
    cin >> s;
    vector<mint> dp(s + 1, 0);
    dp[0] = 1;
    for (auto i = 3; i <= s; i++) {
        dp[i] = dp[i - 3] + dp[i - 1];
        // for (auto j = 0; j <= i - 3; j++) dp[i] += dp[j];
    }
    cout << dp[s] << endl;
    return 0;
}


Measured memory_bytes: 3544
/* ~ Programmer >> Tushar Mahajan */
#include <iostream>
#include <bits/stdc++.h> 
using namespace std;
#define ll long long int
#define ld long double
#define MOD 1000000007
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL); 

int main() {
	ios;
	ll n,r=0,w=0,count = 0;
	cin>>n;
	string s;
	cin>>s;
	for(int i=0;i<n;i++)
	{
	    if(s[i]=='R')
	    {
	        r++;
	    }
	    else
	    {
	        w++;
	    }
	}
	for(int i=0;i<r;i++)
	{
	    if(s[i]=='W')
	    {
	        count++;
	    }
	}
	cout<<min(w,count)<<endl;
	return 0;
}


Measured memory_bytes: 3688
#include <iostream>
#include <algorithm>

#define INF 1e9

using namespace std;

int main() {
    int N, M, R;
    int r[9], G[201][201];

    cin >> N >> M >> R;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N ; j++) {
            G[i][j] = (i == j) ? 0 : INF;
        }
    }

    for (int i = 0; i < R; i++) {
        cin >> r[i]; r[i]--;
    }

    sort(r, r + R);

    for (int i = 0; i < M; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        G[A-1][B-1] = G[B-1][A-1] = C;
    }

    // Warshall–Floyd Algorithm
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
 
    int ans = INF;

    do {
        int t = 0;
        for (int i = 0; i < R-1; i++) {
            t += G[r[i]][r[i+1]];
        }
        ans = min(ans, t);
    } while (next_permutation(r, r + R));

    cout << ans << endl;

    return 0;
}

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

#define REP(i,n) for(int i=0; i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
using namespace std;

int main() {
	int n;
	cin >> n;
	n = sqrt(n);
	cout << n * n << endl;
	return 0;
}

Measured memory_bytes: 256
# AOJ 0516: Maximum Sum
# Python3 2018.6.30 bal4u

a, s = [0]*100003, [0]*100003
while True:
	n, k = map(int, input().split())
	if n == 0: break
	s[0] = a[0] = int(input())
	for i in range(1, n):
		a[i] = int(input())
		s[i] = s[i-1] + a[i]
		if i >= k: s[i] -= a[i-k]
	ans = s[k-1]
	for i in range(k, n):
		if s[i] > ans: ans = s[i]
	print(ans)


Measured memory_bytes: 13316
#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
#include <set>
#include <functional>
typedef long long ll;
using namespace std;

int main(void) {
  ll i, j, k, n, m, h, w, sum = 0, now = 0, num = 0, numn = 0;
  scanf("%lld%lld", &n, &k);
  ll a[n], ans[51];
  bool flg[51];
  for(i = 0; i < n; ++i) scanf("%lld", &a[i]);
  for(i = 0; i < 51; ++i) {
    ans[i] = 0, flg[i] = false;
    for(j = 0; j < n; ++j) {
      if(a[j] & (1ll << i)) ans[i]++;
    }
    if(ans[i] * 2 < n) flg[i] = true, ans[i] = n - ans[i];
  }
  for(i = 0; i < 51; ++i) {
    if((1ll << (i + 1)) <= k) now += ans[i] * (1ll << i);
    else if(!flg[i]) now += ans[i] * (1ll << i);
    else now += (n - ans[i]) * (1ll << i);
  }
  for(i = 0; i < 51; ++i) if(!flg[i]) sum += ans[i] * (1ll << i);
  for(i = 50; i >= 0; --i) if(flg[i]) {
    if((1ll << i) <= k) {
      num = 1ll << i;
      numn = i;
      sum += ans[i] * (1ll << i);
      break;
    } else sum += (n - ans[i]) * (1ll << i);
  }
  ll tp = 0;
  for(i = 0; i < numn; ++i) if(flg[i]) {
    tp += (n - ans[i]) * (1ll << i);
  }
  if(now < sum + tp) now = sum + tp;
  for(i = 0; i < numn; ++i) if(flg[i]) {
    ll tmp = ans[i] * (1ll << i), tnum = num + (1ll << i);
    if(tnum > k) break;
    for(j = i - 1; j >= 0; --j) {
      if(flg[j] && tnum + (1ll << j) <= k) {
        tnum += 1ll << j;
        tmp += ans[j] * (1ll << j);
      } else if(flg[j]) tmp += (n - ans[j]) * (1ll << j);
    }
    for(j = i + 1; j < numn; ++j) if(flg[j]) {
      tmp += (n - ans[j]) * (1ll << j);
    }
    if(sum + tmp > now) now = sum + tmp;
  }
  printf("%lld", now);
  return 0;
}

Measured memory_bytes: 896
n,q=gets.split.map(&:to_i)
word=gets.chomp.to_s

s=[]
s[0]=0
for i in 0..word.length-1
v=0
if i==0
v=0
elsif word[i-1]=="A" && word[i]=="C"
v=1
end

s[i+1]=s[i]+v
end

q.times.each do
v=gets.split.map(&:to_i)
p s[v[1]]-s[v[0]]
end

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

using ll = long long;

#define rep(i, n) for(int i = 0; i < (n); i++)

template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}

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

    int N, Q;
    string S;
    cin >> N >> S >> Q;
    vector<int> K(Q); cin >> K;

    vector<ll> ans(Q);
    vector<int> sumd(N), summ(N);
    vector<ll> sumdm(N);
    sumd[0] = S[0] == 'D';
    summ[0] = S[0] == 'M';
    sumdm[0] = 0;
    for (int i = 1; i < N; i++) {
        sumd[i] = sumd[i-1] + (S[i] == 'D');
        summ[i] = summ[i-1] + (S[i] == 'M');
        sumdm[i] = sumdm[i-1] + (S[i] == 'M' ? sumd[i] : 0);
        if (S[i] == 'C') {
            for (int j = 0; j < Q; j++) {
                const int& k = K[j];
                ans[j] += sumdm[i-1];
                if (i - k >= 0) {
                    ans[j] -=  sumdm[i-k] + (ll)sumd[i-k] * (summ[i-1] - summ[i-k]);
                }
            }
        }
    }

    for (const ll& a : ans) cout << a << endl;
}


Measured memory_bytes: 17052
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

ll n;
ll a;
vector<ll> ve;

int main()
{
    scanf("%lld", &n);
    for(ll i = 0; i < n; i++)
    {
        scanf("%lld", &a);
        ll t = upper_bound(ve.begin(), ve.end(), a, greater<ll>()) - ve.begin();
        if(ve.size() <= t) ve.push_back(a);
        else ve[t] = a;
    }
    cout<<ve.size()<<endl;
    return 0;
}


Measured memory_bytes: 1400
#!/usr/bin/env python3
import sys, heapq
sys.setrecursionlimit(300000)


def solve(N: int, m: int, A: "List[int]", B: "List[int]"):
    p = []
    for i in range(N):
        p.append([A[i], B[i]])
    p.sort(key = lambda x: (x[0], - x[1]))
    #print(p)
    ret = 0
    tmp = 1
    idx = 0
    q = []
    while tmp <= m:
        while idx < len(p) and p[idx][0] <= tmp:
            heapq.heappush(q, -p[idx][1])
            idx += 1
        #print(q)
        if len(q) > 0:
            head = heapq.heappop(q)
            ret += -head
        tmp += 1
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]" 
    B = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 32352
#include<stdio.h>

int main(){
	int a,b,sx,sy,tx,ty,i;
	scanf("%d %d %d %d",&sx,&sy,&tx,&ty);
	 a=tx-sx;
	 b=ty-sy;
	for(i=0;i<b;i++) printf("U");
	for(i=0;i<a;i++) printf("R");
	for(i=0;i<b;i++) printf("D");
	for(i=0;i<=a;i++) printf("L");
	for(i=0;i<=b;i++) printf("U");
	for(i=0;i<=a;i++) printf("R");
	printf("DR");
	for(i=0;i<=b;i++) printf("D");
	for(i=0;i<=a;i++) printf("L");
	printf("U\n");
	return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include <string>



using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)


map<string, int> mp;
#define ll long long

int main() {
    int a, b;
    cin >> a >> b;
    if (a <= 0 && b >= 0) {
        cout << "Zero" << endl;
        return 0;
    }
    if (a > 0) {
        cout << "Positive" << endl;
        return 0;
   }
    if (b < 0) {
        if ((b - a) % 2 == 0) {
            cout << "Negative" << endl;
            return 0;
        }
        else {
            cout << "Positive" << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
import numpy as np

n, k = map(int, input().split())
h_arr = np.array(list(map(int, input().split())))
cost_arr = np.zeros(n, dtype=int)
for i in range(1, n):
    start = max(i-k, 0)
    cost_arr[i] = min(abs(h_arr[start:i] - h_arr[i]) + cost_arr[start:i])
print(int(cost_arr[-1]))


Measured memory_bytes: 22808
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
int main() {
	string s;
	cin >> s;
	int cnt = 0;
	if (s[0] == 'R' or s[1] == 'R' or s[2] == 'R')
		cnt = 1;
	if ((s[0] == s[1] and s[0] == 'R') or (s[1] == s[2] and s[1] == 'R'))
		cnt = 2;
	if (s[0] == 'R' and s[1] == 'R' and s[2] == 'R')
		cnt = 3;
	cout << cnt << endl;
}

Measured memory_bytes: 3620