akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

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

    map<string, int> m;
    m["SSS"] = 0;
    m["SSW"] = 1;
    m["SWS"] = 2;
    m["SWW"] = 3;
    m["WSS"] = 4;
    m["WSW"] = 5;
    m["WWS"] = 6;
    m["WWW"] = 7;

    vector<vector<int>> diag(n, vector<int>(8, -1));
    if (s[0] == 'o') {
        diag[0][m["SSS"]] = 40;
        diag[0][m["SWW"]] = 51;
        diag[0][m["WSW"]] = 62;
        diag[0][m["WWS"]] = 73;
    } else {
        diag[0][m["SSW"]] = 40;
        diag[0][m["SWS"]] = 51;
        diag[0][m["WSS"]] = 62;
        diag[0][m["WWW"]] = 73;
    }

    for (int i = 1; i < n; i++) {
        if (s[i] == 'o') {
            diag[i][m["SSS"]] =
                    (diag[i - 1][m["SSS"]] != -1 ? m["SSS"] : (diag[i - 1][m["WSS"]] != -1 ? m["WSS"] : -1));
            diag[i][m["SWW"]] =
                    (diag[i - 1][m["SSW"]] != -1 ? m["SSW"] : (diag[i - 1][m["WSW"]] != -1 ? m["WSW"] : -1));
            diag[i][m["WSW"]] =
                    (diag[i - 1][m["SWS"]] != -1 ? m["SWS"] : (diag[i - 1][m["WWS"]] != -1 ? m["WWS"] : -1));
            diag[i][m["WWS"]] =
                    (diag[i - 1][m["SWW"]] != -1 ? m["SWW"] : (diag[i - 1][m["WWW"]] != -1 ? m["WWW"] : -1));
        } else {
            diag[i][m["SSW"]] =
                    (diag[i - 1][m["SSS"]] != -1 ? m["SSS"] : (diag[i - 1][m["WSS"]] != -1 ? m["WSS"] : -1));
            diag[i][m["SWS"]] =
                    (diag[i - 1][m["SSW"]] != -1 ? m["SSW"] : (diag[i - 1][m["WSW"]] != -1 ? m["WSW"] : -1));
            diag[i][m["WSS"]] =
                    (diag[i - 1][m["SWS"]] != -1 ? m["SWS"] : (diag[i - 1][m["WWS"]] != -1 ? m["WWS"] : -1));
            diag[i][m["WWW"]] =
                    (diag[i - 1][m["SWW"]] != -1 ? m["SWW"] : (diag[i - 1][m["WWW"]] != -1 ? m["WWW"] : -1));
        }
    }

    int rev = -1;
    for (int i = 0; i < 8; i++) {
        int r = diag[n - 1][i];
        for (int j = n - 2; j >= 0 && r >= 0; j--) {
            r = diag[j][r];
        }

        if (r >= 0 && ((i < 4 && i == r % 10) || (i >= 4 && i == r / 10))) {
            rev = i;
        }
    }

    if (rev == -1) {
        cout << "-1" << endl;
    } else {
        vector<string> res(n);
        for (int i = n - 1, r = rev; i >= 0; i--) {
            res[i] = (diag[i][r] % 2 == 0 ? "S" : "W");
            r = diag[i][r];
        }

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


Measured memory_bytes: 12928
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace AtCoder
{
    class ABC179C
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            //string[] str = Console.ReadLine().Split(' ');
            int count = 0;
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <= n/i; j++)
                {
                    if(i*j<n)
                    {
                        count++;
                    }
                }
            }
            Console.WriteLine(count);
        }
    }
}

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

int main(){
  int X;
  cin >> X;
  int max=0;
  for(int i=2; i<=9; i++){
    for(int j=sqrt(X)+1; j>=1; j--){
      if(max<(int)pow(j,i) && (int)pow(j,i)<=X){
        max = (int)pow(j,i);
      }
    }
  }
  cout << max << endl;
  return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <fstream>

using namespace std;

typedef unsigned uint;
typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair
#define MSG(a) cout << #a << " = " << a << endl;
#define rep(i, n) for(int i = 0; i < n; i++)

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

const int MAX_N = 1000;

struct cross
{
	int right_num, left_num;
	int right_point, left_point;
	int r, l, h;
};

bool cross_omp(const cross &left, const cross &right)
{	return left.h < right.h;	}


int main()
{
	int n, m, h, k;

	while( cin >> n >> m >> h >> k && n )
	{
		int points[1005];
		vector<cross> crosses;

		rep(i, n)
			cin >> points[i];
		
		rep(i, m)
		{
			cross c;
			cin >> c.l >> c.h;
			c.r = c.l + 1;

			crosses.push_back(c);
		}

		sort(crosses.begin(), crosses.end(), cross_omp);

		
		int work[1001];

		// from up
		rep(i, n)
			work[i+1] = i+1;

		rep(i, m)
		{
			crosses[i].left_num = work[crosses[i].l];
			crosses[i].right_num = work[crosses[i].r];

			swap(work[crosses[i].l], work[crosses[i].r]);
		}


		// from down
		rep(i, n)
			work[i+1] = points[i];

		for(int i = m - 1; 0 <= i; i--){
			crosses[i].left_point = work[crosses[i].l];
			crosses[i].right_point = work[crosses[i].r];

			swap(work[crosses[i].l], work[crosses[i].r]);
		}


		int score = 0;
		rep(i, k)
			score += work[i+1];

		int max = 0;
		rep(i, m)
		{
			// out of range
			if( ( crosses[i].left_num <= k && crosses[i].right_num <= k )
				|| ( crosses[i].left_num > k && crosses[i].right_num > k ) )
					continue;


			// right
			if(crosses[i].left_num <= k)
			{
				if( crosses[i].left_point >= crosses[i].right_point )
					continue;

				chmax(max, crosses[i].right_point - crosses[i].left_point);
			}


			// left
			if(crosses[i].right_num <= k)
			{
				if( crosses[i].left_point <= crosses[i].right_point )
					continue;
				
				chmax(max, crosses[i].left_point - crosses[i].right_point);
			}
		}


		cout << score - max << endl;
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
 
int m, n;
int p[101010];
int c[505], e[505];
 
int dp[512][10101];
 
int dfs(int i = 0, int sum = 0, int cost = 0)
{
  if (i == n){
    return 0;
  }
  int &ret = dp[i][sum];
  if (ret != -1) return ret;
 
  int v = min(sum + c[i], m);
  ret = max(dfs(i + 1, v, cost + e[i]) + p[v] - p[sum] - e[i], dfs(i + 1, sum, cost));
  ret = max(0, ret);
 
  return ret;
}
 
int main()
{
  memset(dp, -1, sizeof(dp));
  cin >> m >> n;
  for (int i = 1; i <= m; i++){
    cin >> p[i];
  }
  sort(p + 1, p + m + 1, greater<int>());
  for (int i = 1; i <= m; i++){
    p[i] += p[i - 1];
  }
 
  for (int i = 0; i < n; i++){
    cin >> c[i] >> e[i];
  }
 
  cout << dfs() << endl;
}

Measured memory_bytes: 23412
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
const int N = 1000000;

int main() {
   string s; cin >> s;
   
   if((s[0] == 'A' && s[1] == 'A' && s[2] == 'A') ||(s[0] == 'B' && s[1] == 'B' && s[2] == 'B'))print("No");
   else print("Yes");
}

Measured memory_bytes: 256
import numpy as np
N, W = map(int,input().split())
ls = []
for i in range(N):
  w, v = map(int, input().split())
  ls += [[w,v]]
ls = np.array(ls)
w1 = ls[0][0]
ls[:,0] -= w1

M = 3*N
dp = np.full((N+1,M+1), -float('inf'))
dp[0][0] = 0

for i in range(N):
  w, v = ls[i]
  dp[1:,w:] = np.maximum(dp[1:,w:], dp[:N,:M-w+1]+v)
  
ans = 0
for i in range(1,N+1):
  B = i*w1
  m = 0
  for j in range(M+1):
    if B+j<=W:
      m = max(m,dp[i][j])
  if ans<m:
    ans = m
print(int(ans))


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

#define int long long
#define double long double
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) begin(x), end(x)
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr double pi = 3.1415926535897932384626433832795028L;
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int H, W;
signed main() {
    cin >> H >> W;
    if (H == 1 || W == 1) { fin(1); }
    cout << (H / 2) * W + (H % 2) * ((W + 1) / 2) << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<bits/stdc++.h>
#include<string>
#include<vector> 
///std::string;
using namespace std;
int main(){
  int n,k;
  std::cin >> n>> k;
  vector<int > V(n,0);
  for(int i=0;i<k;i++){
      int d;
      cin>>d;
      for(int j=0;j<d;j++){
          int n;
          cin>>n;
          V[n-1]++;
      }
  }
  int result=0;
  for(int i=0;i<n;i++){
      if(V[i]==0){
          result++;
      }
  }
  cout<<result;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>

#include <sstream>

using namespace std;

int main(){
  int n;
  vector<int> s;
  int q;
  vector<int> t;
  
  cin >> n;
  for(int i=0;i<n;i++){
    int tmp;
    cin >> tmp;
    s.push_back(tmp);
  }
  
  cin >> q;
  for(int i=0;i<q;i++){
    int tmp;
    cin >> tmp;
    t.push_back(tmp);
  }

  int cnt=0;
  for(int i=0;i<q;i++){
    for(int j=0;j<n;j++){
      if(s[j]==t[i]){
	cnt++;
	break;
      }
    }
  }

  cout << cnt << endl;
      // t[i]???s????????????
      
      
     
  



      
  

}

Measured memory_bytes: 1320
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll dp[3005][3005];
void lcs(string &s, string &t, ll m, ll n){
    for(ll i=0;i<=m;i++){
        for(ll j=0;j<=n;j++){
            if(i==0 || j==0){
                dp[i][j] = 0;
            }
            else if(s[i-1] == t[j-1]){
                dp[i][j] = 1 + dp[i-1][j-1];
            }
            else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(dp,-1,sizeof(dp));
    string s,t;
    cin>>s>>t;
    ll m = s.length();
    ll n = t.length();
    lcs(s,t,m,n);
    string ans = "";
    ll i = m, j = n;
    while(i > 0 && j > 0){
        if(s[i-1] == t[j-1]){
            ans.push_back(t[j-1]);
            i--;
            j--;
        }
        else if(dp[i-1][j] > dp[i][j-1]){
            i--;
        }
        else{
            j--;
        }
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<"\n";
}


Measured memory_bytes: 70784
import java.util.*;
import java.lang.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		long[] prime = new long[200];
		prime[0] = 2;
		prime[1] = 3;
		int a = 2;
		for( int i=3; i<1000; i+=2 ){
			for( int j=i-1; j>=3; j-- ){
				if( i%j==0 ){
					break;
				}
				if( j==3 ){
					prime[a]=i;
					a++;
				}
			}
		}
		long[] countPrime = new long[a];
		for( int i=2; i<=N; i++ ){
			for( int j=0; j<a; j++ ){
				long b = i;
				for( int k=0; k<i/2; k++ ){
					if( b%prime[j]==0 ){
						countPrime[j]++;
						b = b/prime[j];
					}else{
						break;
					}
				}	
			}         
		}
		long ans = 1;
		long mod = 1000000007L;      
		for( int i=0; i<a; i++ ){
			countPrime[i]++;          
			ans = ((ans%mod)*(countPrime[i]%mod))%mod;
		}    
		System.out.println(ans);
	}
}


Measured memory_bytes: 22740
//start of jonathanirvings' template v3.0.3 (BETA)

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  #ifndef TESTING
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
  #endif
}

//end of jonathanirvings' template v3.0.3 (BETA)

int n;
int data[100005];

int main()
{
  scanf("%d",&n);
  REP(i,n) scanf("%d",&data[i]);
  SORTA(data,n);
  LL now = 0;
  int risan = 0;
  REP(i,n)
  {
    if (data[i] > 2 * now) risan = 1;
    else risan++;
    now += data[i];
  }
  printf("%d\n",risan);
  return 0;
}










Measured memory_bytes: 640
k = int(input())
# a,bの最大公約数


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            t = gcd(gcd(a, b), c)
            ans += t
print(ans)


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

using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
#define REP(i, n) for(int i=1;i<=n;i++)
typedef long long ll;

const int INF = 1000000000;
int dp[1000005];
int dp2[1000005];

int main() {
	vector<ll> shimentaisuu(200);
	REP(i, 200) {
		shimentaisuu[i] = i * (i + 1) * (i + 2) / 6;
	}
	
	vector<int> input;
	
	while (true) {
		int n;
		cin >> n;
		if (n == 0) break;
		input.push_back(n);
	}
	
	dp[0] = 0;
	dp2[0] = 0;
	for (int i = 1; i <= 1000000; ++i) {
		dp[i] = INF;
		dp2[i] = INF;
		REP(j, 200) {
			if (shimentaisuu[j] > i) break;
			dp[i] = min(dp[i], dp[i - shimentaisuu[j]] + 1);
			if (j % 4 == 1) {
				dp2[i] = min(dp2[i], dp2[i - shimentaisuu[j]] + 1);
			}
		}
	}
	
	rep(i,input.size()){
		cout << dp[input[i]] << " " << dp2[input[i]] << endl;
	}
	
	
	return 0;
}




Measured memory_bytes: 10892
#include<iostream>

using namespace std;

int main(){
	int k;
	cin >> k;
	int ans = 0;
	if(k % 2 == 0){
		ans = (k/2) * (k/2);
	}else{
		ans = (k/2) * (k/2 + 1);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 101
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INF 2010
#define NIL -1

int G[N][N];
int n;

int prim(void) {
  int i, mincost, u, num = 0;
  int d[N], pi[N], color[N];

  for(i = 1; i <= n; i++) {
    d[i] = INF;
    pi[i] = NIL;
    color[i] = WHITE;
  }
  d[1] = 0;
  while(1) {
    mincost = INF;
    for(i = 1; i <= n; i++) {
      if(color[i] != BLACK && d[i] < mincost) {
        mincost = d[i];
        u = i;
      }
    }
    if(mincost == INF) break;
    color[u] = BLACK;
    for(i = 1; i<= n; i++) {
      if(G[u][i] != -1) {
        if(color[i] != BLACK && G[u][i] < d[i]) {
          pi[i] = u;
          d[i] = G[u][i];
        }
      }
    }
  }
  for(i = 1; i <= n; i++) {
    num += d[i];
  }
  return num;
}

int main() {
  int i, j, k;

  scanf("%d", &n);
  for(i = 1; i <= n; i++) {
    for(j = 1; j <= n; j++) {
      scanf("%d", &G[i][j]);
    }
  }
  k = prim();
  printf("%d\n", k);

  return 0;
}

Measured memory_bytes: 640
N = int(input())
a = list(map(int,input().split()))

d = {}
cnt = 0
for i in range(N):
    if 1<=a[i]<=399:
        if 'gray' in d.keys():
            d['gray'] += 1
        else:
            d['gray'] = 1
    elif 400<=a[i]<=799:
        if 'brown' in d.keys():
            d['brown'] += 1
        else:
            d['brown'] = 1
    elif 800<=a[i]<=1199:
        if 'green' in d.keys():
            d['green'] += 1
        else:
            d['green'] = 1
    elif 1200<=a[i]<=1599:
        if 'light_blue' in d.keys():
            d['light_blue'] += 1
        else:
            d['light_blue'] = 1
    elif 1600<=a[i]<=1999:
        if 'blue' in d.keys():
            d['blue'] += 1
        else:
            d['blue'] = 1
    elif 2000<=a[i]<=2399:
        if 'yellow' in d.keys():
            d['yellow'] += 1
        else:
            d['yellow'] = 1
    elif 2400<=a[i]<=2799:
        if 'orange' in d.keys():
            d['orange'] += 1
        else:
            d['orange'] = 1
    elif 2800<=a[i]<=3199:
        if 'red' in d.keys():
            d['red'] += 1
        else:
            d['red'] = 1
    else:
        cnt += 1
if len(d) == 0:
    print(1,len(d)+cnt)
else:
    print(len(d),len(d)+cnt)

Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
using ll = long long;
int main() {
  int h, w, a, b;
  cin >> h >> w >> a >> b;
  cout << (h - a) * (w - b) << endl;
  return 0;
}

Measured memory_bytes: 3560
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int e = 4*1e6 + 69;
const int mod = 1e9 + 7;

ll a[e];


int main()
{
    ll n, m;
    cin >> n >> m;
    if(abs(n - m) % 2 == 0)
    {
        cout << abs(n + m)/2;
    }
    else
    {
        cout <<"IMPOSSIBLE";
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main(){    
  int N;
  cin >> N;
  if(N%2 == 0) cout << 1/2.0 << endl;
  else{cout << (N+1)/(2.0*N)*1.0 << endl;
    
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <tuple>
#include <math.h>
#include <deque>
#include <stack>

using namespace std;

typedef long long ll;

int main(void){
    ll a,b;
    cin >> a >> b;
    ll ans = max(a + b,max(a * b, a - b));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
def examA():
    ABC =LI(); ABC.sort()
    if ABC[0]==ABC[-1]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    N = I()
    S = SI()
    red = S.count("R")
    if red>N//2:
        print("Yes")
    else:
        print("No")
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""

"""

Measured memory_bytes: 3572
main(){
  int i,j,n;
  scanf("%d",&n);
  int a[n][10],b,c;
  for(i=0;i<n;i++)
    for(j=0;j<10;j++)
      scanf("%d",&a[i][j]);
  for(i=0;i<n;i++){
    b=0;
    c=0;
    for(j=0;j<10;j++)
      if(a[i][j]>b)
	b=a[i][j];
      else if(a[i][j]>c)
	c=a[i][j];
      else
	break;
    if(j==10)
      puts("YES");
    else
      puts("NO");
  }
  return 0;
}

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

int main() {
  int a,b;
  cin >> a >> b;
  int c;
  int s = 0;
  for(int i=0;i<b;i++){
   cin >> c;
    s += c;
  }
  if(a>=s){
    cout << a - s << endl;
  }
  else{
    cout << "-1" << endl;
  }
}


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

int main() {
    int n,x;
    cin>>n>>x;
    int mn=1000;
    for (int i=0;i<n;i++) {
        int a;
        cin>>a;
        x-=a;
        mn=min(mn,a);
    }
    cout<<n+x/mn<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<map>
using namespace std;
    int main(void){
    string a,b;
    cin>>a>>b;
    if(a.size()>b.size()){
        cout<<"GREATER"<<endl;
    }
    else if(a.size()<b.size()){
        cout<<"LESS"<<endl;
    }
    else if(a>b){
        cout<<"GREATER"<<endl;
    }
    else if(a<b){
        cout<<"LESS"<<endl;
    }else if(a==b) {
        cout<<"EQUAL"<<endl;
    }
  
    return 0;
}

Measured memory_bytes: 256
//#include <tourist>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1e9;
const ll LINF = ll(1e18);
const int MOD = 1000000007;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define debug(v)          \
    cout << #v << ":";    \
    for (auto x : v)      \
    {                     \
        cout << x << ' '; \
    }                     \
    cout << endl;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
//cout<<fixed<<setprecision(15);有効数字15桁
//-std=c++14
//-std=gnu++17
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a+=b;
    c+=d;
    if(a==c)cout<<"Balanced"<<"\n";
    else if(a<c)cout<<"Right"<<"\n";
    else cout<<"Left"<<"\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
//#define int long long  
int main(){
    int N,K,A=1;
    cin >> N >> K;
    REP(i,N){
        A=min(A*2,A+K);
    }
    cout << A << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

typedef struct{
	int x;
	int y;
}Stu;

typedef struct{
	int x;
	int y;
}Cp;

int abs(int num)
{
	if(num < 0)
		return -1*num;
	else
		return num;
}

int main(void)
{
	int n, m;
	Stu stu[50];
	Cp cp[50];
	int i, j;
	
	scanf("%d %d", &n, &m);
	for(i=0; i<n; i++)
		scanf("%d %d", &stu[i].x, &stu[i].y);
	for(i=0; i<m; i++)
		scanf("%d %d", &cp[i].x, &cp[i].y);
	
	
	for(i=0; i<n; i++){
		int best_cp = 1;
		int mht = abs(stu[i].x-cp[0].x)+abs(stu[i].y-cp[0].y);	//マンハッタン距離
		
		for(j=1; j<m; j++){
			if( mht > abs(stu[i].x-cp[j].x)+abs(stu[i].y-cp[j].y) ){
				mht = abs(stu[i].x-cp[j].x)+abs(stu[i].y-cp[j].y);
				best_cp = j+1;
			}
		}
		
		printf("%d\n", best_cp);
	}
	
	
	return 0;
}


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

using namespace std ;

const int MAX = 100 + 10 ;

long double arr[MAX] ;
int n ;
long double m ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m ;
	long double sum = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		cin>>arr[i] ;
		sum += arr[i] ;
	}
	long double a = 1.00 ;
	a /= (4.00 * m) ;
	int ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		long double b = (arr[i] / sum) ;
		if(b >= a)
			ans++ ;
	}
	if(ans >= m)
		cout<<"Yes\n" ;
	else
		cout<<"No\n" ;
	return 0 ;
}		

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<ios>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<string>
#include<list>
#include<utility>
#include<tuple>
#include<map>
#include<unordered_map>
#include<complex>
using namespace std;
typedef long long llong;
llong gcd(llong a, llong b) {
	if (a < b) std::swap(a, b);
	if (a % b == 0) return b;
	else return gcd(b, a % b);
}
llong lcm(llong a, llong b) {
	llong g = gcd(a, b);
	return a * b / g;
}
//ここまで共通
int N;
class A {
public:
	int x;
	int y;
	int h;
};
vector<A> B;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y, h;
		cin >> x >> y >> h;
		A b;
		b.x = x; b.y = y; b.h = h;
		B.push_back(b);
	}
	int X, Y;
	int hj;
	bool f;

	for (int i = 0; i <= 100; i++) {
		for (int j = 0; j <= 100; j++) {
			int H;
			f = true;
			for (int k = 0; k < N; k++) {
				if (B[k].h == 0) continue;

				H = B[k].h + abs(B[k].x - i) + abs(B[k].y - j);
				break;
			}
			for (int k = 0; k < N; k++) {
				int h = H - abs(B[k].x - i) - abs(B[k].y - j);
				if (h < 0) h = 0;
				if (h != B[k].h) f = false;
			}
			if (f) {
				X = i;
				Y = j;
				hj = H;
				break;
			}
		}
		if (f) break;
	}

	cout << X << ' ' << Y << ' ' << hj << endl;

	return 0;
}

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll gcd(ll a, ll b) {
    if (a < b)
        swap(a, b);
    ll c = a % b;
    if (c == 0)
        return b;
    return gcd(b, c);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    if (N % K == 0) {
        cout << 0 << endl;
    }
    else {
        ll m = N % K;
        cout << std::min(m, abs(K - m)) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

pub fn read_n<T: FromStr>(n: u32) -> Vec<T> {
  read_n_logic::<T>(n, vec![])
}

pub fn read_n_logic<T: FromStr>(n: u32, mut a: Vec<T>) -> Vec<T> {
  match n {
    0 => a,
    _ => {
      a.push(read::<T>());
      read_n_logic(n - 1, a)
    }
  }
}

use std::cmp;

use std::collections::BTreeMap;
use std::collections::BinaryHeap;
fn main() {

  let n = read::<u32>();
  let m = read::<i64>();
  let a = read_n::<i64>(n);
  let mut bh_a: BinaryHeap<i64> = BinaryHeap::new();

  let mut sum = 0;

  for i in a {
    bh_a.push(-i);
  }

  let mut bmap: BTreeMap<i64, i64> = BTreeMap::new();

  for _ in 0..m {
    let b = read::<i64>();
    let c = read::<i64>();
    if bmap.contains_key(&c) {
      let mut temp = bmap.get_mut(&c).unwrap();
      *temp += b;
    } else {
      bmap.insert(c, b);
    }
  }

  let mut done = false;

  for (idx, val) in bmap.iter().rev() {

    for i in 0..*val {
      let bh_a_pop = match bh_a.pop() {
        Some(s) => s,
        None => {
          done = true;
          break;
        }
      };

      if -bh_a_pop >= *idx {
        bh_a.push(bh_a_pop);
        done = true;
        break;
      } else {
        bh_a.push(-idx);
      }
    }

    if done {
      break;
    }
  }

  let sum_bh_a: i64 = bh_a.iter().sum();
  println!("{}", -sum_bh_a);

}

fn get_maxinum(bmap: &mut BTreeMap<i64, i64>) -> i64 {
  let mut found_num = 0;
  for (idx, val) in bmap.iter().rev() {
    if *val > 0 {
      found_num = *idx;
      break;
    }
  }
  found_num
}

fn subscribe_bmap(bmap: &mut BTreeMap<i64, i64>, used_index: &i64) {
  if bmap.contains_key(used_index) {
    let mut temp = bmap.get_mut(used_index).unwrap();
    *temp -= 1;
  }
}


Measured memory_bytes: 17788
while True:
  n = int(input())
  if not n:
    break

  start = int(input()) - 1 #開始の位置
  goal = int(input()) - 1  #あたりの位置
  d = int(input())
  
  nums = [[i for i in range(n)]] #各段での数字の並び
  bars = [] #横棒リスト
  
  for i in range(d):
    s = input()
    bars.append(s)
    new = nums[-1][:]

    for j in range(n - 1):
      if s[j] == "1": #横棒があれば入れ替え
        new[j], new[j + 1] = new[j + 1], new[j]

    nums.append(new)
    
  to_goal = nums[-1][goal] #あたりにたどり着く初期位置
  
  if to_goal == start: #元からあたりにたどり着く場合
    print(0)

  else: #各段について、to_goalとスタートが隣り合うかチェック
    for i, status in enumerate(nums[1:]):
      to_goal_ind = status.index(to_goal) #to_goalの位置
      start_ind = status.index(start)     #startの位置
      ind1, ind2 = min(to_goal_ind, start_ind), max(to_goal_ind, start_ind)
  
      if (ind2 - ind1 == 1                               #隣り合っていて、 
          and bars[i][ind1] == "0"                       #該当位置と
          and (ind1 == 0 or bars[i][ind1 - 1] == "0")    #左と
          and (ind2 == n - 1 or bars[i][ind2] == "0")):  #右に、辺がなければ出力
          print(i + 1, ind1 + 1)
          break
    else:
      print(1)



Measured memory_bytes: 5616
import java.util.*;
public class Main {
	public static void myout(Object text){//standard output
		System.out.println(text);
	}
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		//String tmp = sc.next();
		//int tmp = sc.nextInt();
		//Long tmp = sc.nextLong();
      Long output = new Long(0);
      int N = sc.nextInt();
      int M = sc.nextInt();
      PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Comparator.reverseOrder());
      int i;
      for(i = 0; i < N; i++){
        pq.add(sc.nextInt());
      }
      for(i = 0; i < M; i++){
        int max = pq.poll();
        pq.add(max / 2);
      }
      for(i = 0; i < N; i++){
        output += pq.poll();
      }
      myout(output);
	}
}


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

using namespace std;
using llong = long long;
using ldbl = long double;
using lpair = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

const llong inf = 1100100100100100ll;
const llong mod = 1e9+7;

int main() {
	llong N;
	vector<string> s;

	cin >> N;
	s.resize(N);
	for (int i = 0; i < N; ++i) {
		cin >> s[i];
		sort(ALL(s[i]));
	}

	map<string, llong> m;
	for (auto x : s)
		m[x]++;

	llong ans = 0;
	for (auto it = m.begin(); it != m.end(); ++it) {
		ans += it->second * (it->second-1)/2ll;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 18176
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n,k=map(int,input().split())
if (n-1)*(n-2)//2<k:
    print(-1)
    quit()
print(n-1+(n-1)*(n-2)//2-k)
for i in range(n-1):
    lst=[1,i+2]
    print(*lst)

lst=[]
for i in range(n-1):
    for j in range(n-2-i):
        lst.append([i+2,i+2+j+1])
# print(lst)
for i in range((n-1)*(n-2)//2-k):
    print(*lst[i])
    

Measured memory_bytes: 68972
S = input()
S = S[::-1]

divide = ["dream", "dreamer", "erase", "eraser"]

for i, r in enumerate(divide):
    divide[i] = r[::-1]

#a : 開始インデックス
#b : 終了インデックス

a = 0
while a < len(S):
    can = False
    for i in range(4):
        d = divide[i]
        d_size = len(d)
        b = a + d_size
        if S[a:b] == d:
            can = True
            a = b
    if can == False:
        break

if can:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3188
#include <iostream>
using namespace std;
int main() {
    int h, w;
    while(1) {
        cin >> h >> w;
        if (h == 0 && w == 0) break;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (i == 0 || i == h - 1 || j == 0 || j == w - 1) {
                    cout << "#";
                } else {
                    cout << ".";
                }
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3088
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue = BinaryHeap!(Array!long, "a<b");
// dfmt on

/// Number of k-combinations
T combination(T = long)(T n, T k)
{
    assert(0 <= k);
    assert(0 <= n);
    if (n < k)
        return 0;
    k = min(n - k, k);
    if (k == 0)
        return 1;
    if (k == 1)
        return n;
    return memoize!combination(n - 1, k - 1) + memoize!combination(n - 1, k);
}

void main()
{
    long N = lread();
    auto G = new bool[][](N, N);
    long cnt;
    foreach (i; 0 .. N - (N & 1))
    {
        long a = i;
        long b = (N - (N & 1)) - i - 1;
        if (b < a)
            continue;
        G[a][b] = G[b][a] = true;
        if (a != b)
            cnt++;
    }
    writeln((((N - 1) * N) / 2) - cnt);
    foreach (i; 0 .. N)
        foreach (j; i + 1 .. N)
            if (!G[i][j])
            {
                writefln("%d %d", i + 1, j + 1);
            }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int Array[1005];

int FindMinPrice( int N , int k ){
    int i , Ans = 0;
    sort( Array + 1 , Array + N + 1 );

    for( i = 1 ; i <= k ; ++i )
        Ans += Array[i];
    
    return Ans;
}

int main(){
    int N , k , i;
    scanf( "%d%d" , &N , &k );

    for( i = 1 ; i <= N ; ++i )
        scanf( "%d" , Array + i );

    printf( "%d\n" , FindMinPrice( N , k ) );
    return 0;
}

Measured memory_bytes: 3824
#pragma GCC optimze("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}

int powm(int a, int b, int mod) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}

void solve() {
	string s;
	cin>>s;
	string t="";
	while(sz(t)<sz(s)) {
		t+="hi";
	}
	if(s==t)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
}

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(8);
	int t=1;
//	cin>>t;
	while(t--)
		solve();
#ifdef rd
	cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
#endif
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define ii pair<int, int>
#define int long long
using namespace std;

const int mod = 998244353;
int a[1000005];
int f[3005][6005];
int n, s;

int attempt(int i, int w)
{

    if (i > n)
    {
        if (w == s)
            return 1;
        return 0;
    }

    if (f[i][w] != -1)
        return f[i][w];
    int res = 0;

    res = (res + 2 * attempt(i+1, w))%mod;

    if (w + a[i] <= s)
        res = (res + attempt(i+1, w + a[i]))%mod;

    return f[i][w] = res;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen("depart.inp", "r", stdin);
//    freopen("depart.out", "w", stdout);

    memset(f, -1, sizeof(f));
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    cout << attempt(1, 0) %mod;
}


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

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

    string ans = "";
    for (int i = 0; i < s.size(); i++)
    {
        switch (s[i])
        {
        case '0':
            ans += "0";
            break;
        case '1':
            ans += "1";
            break;
        case 'B':
            if (!ans.empty())
            {
                ans.pop_back();
            }
            break;
        default:
            break;
        }
    }
    cout << ans << endl;
}


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

int main()
{
    cin>>x;
    while(1){
        bool xb=true;
        for (int i=2;i<sqrt(x);++i){
            if(x%i==0){
                xb=false;
                break;
            }
        }
        if (xb){
            break;
        }
        ++x;
    }
    cout<<x<<endl;
}

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

int main(){
  string s;
  cin >> s;
  int n = s.size();

  int left = 0;

  long long ans = 0;
  for(int i = 0;i < n;i++){
    if(s[i] == 'W'){
      ans += i-left;
      left++;
    }
  }

  cout << ans << endl;

  return 0;
}

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

using namespace std;

const int md = 1000000007;

const int N = 1234567;

pair <int, int> a[N];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n + n; i++) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a, a + n + n);
  int ans = 1;
  int balance = 0;
  for (int i = 0; i < n + n; i++) {
    if (a[i].second < n) {
      if (balance < 0) {
        ans = (long long) ans * (-balance) % md;
      }
      balance++;
    } else {
      if (balance > 0) {
        ans = (long long) ans * balance % md;
      }
      balance--;
    }
  }
  printf("%d\n", ans);
  return 0;
}


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

using namespace std;
typedef long long ll;
typedef long double ld;
using graph = vector<vector<int>>;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repd(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define all(x) (x).begin(),(x).end()
#define size(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000

#define pb push_back
#define mp make_pair
#define f first
#define s second

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 (b<a) { a=b; return true; } return false; }

#define FIND(a,b) find(all(a),b)!=a.end()

int main(){
	int n,m,x;cin>>n>>m>>x;
	vector<int> l(0);
	int a;
	int ansl=0,ansr=0;
	rep(i,m){
		cin>>a;
		if(min(n,x)<a&&a<max(n,x))ansl++;
		if(a<x)ansr++;
	}
	cout << min(ansl,ansr)<<endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define check system("pause")
#define all(x) (x).begin(),(x).end()
#define de(a) cout<<#a<<" = "<<a<<endl
#define dd(a) cout<<#a<<" = "<<a<<" "
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 0x3f3f3f3f
const ll mod = 1e9+7;
const int N = 1e6+20;
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define mes(p,b) memset(p,b,sizeof(p))
#define sz(x) int(x.size())
int n,k,d,x,a[101];
int main()
{
  	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	mes(a,0);
	rep(i,1,k){
		cin>>d;
		while(d--){
			cin>>x;
			a[x]=1;
		
		}
	}
	int ans=0;
	rep(i,1,n) if(!a[i]) ans++;
	cout<<ans;
  	return 0;
}



Measured memory_bytes: 3656
#include <iostream>

int main() {
    int N;
    bool flag = true;
    std::cin >> N;
    for (int i = 0; i < N && flag; i++) {
        int temp = 0;
        std::cin >> temp;
        if (temp % 2 == 0) {
            if ((temp % 3 != 0) && (temp % 5 != 0)) {
                flag = false;
            }
        }
    }
    if (flag) {
        std::cout << "APPROVED\n";
    }
    else {
        std::cout << "DENIED\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <deque>
#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <string>
#include <vector>

using namespace std;

#define int long long

#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

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

#define debug(x) cerr << #x << ": " << x << endl;

const int MOD = 1e9 + 7;

signed main(void)
{
  int num;
  int n, m; cin >> n >> m;
  vector<vector<int>> v(m);
  for (int i = 0; i < n; ++i) {
    int a, b; cin >> a >> b;
    if (a <= m)
      v[a - 1].push_back(b);
  }

  num = 0;
  priority_queue<int> q;
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < v[i].size(); ++j) {
      q.push(v[i][j]);
    }
    if (q.empty()) continue;
    num += q.top();
    q.pop();
  }
  cout << num << endl;
}


Measured memory_bytes: 5632
while True:
    a,b = map(int,input().split())
    if a==0 and b==0:
        break
    if a<b:
        a,b = b,a
    p=0
    while b != 0:
        c = a % b
        a,b = b,c
        p += 1
    print(a,p)



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

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define pb push_back
#define mp make_pair
#define SZ(a) ((int)(a.size()))
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> PI;

const int MAX_N=600;
int a[MAX_N];
int b[MAX_N];
bool vis[MAX_N];
int match[MAX_N];
int n,m;

int gcd[500][500];
vector<int> G[500];

bool aug(int cv){
  vis[cv] = 1;
  for(auto j : G[cv]){
    if(match[j] == -1 ||
       (!vis[match[j]] && aug(match[j]))){
      match[j] = cv;
      return true;
    }
  }
  return false;
}

int main(int argc, char *argv[])
{
  while(cin >> m >> n, n){
    rep(i,500) G[i].clear();
    rep(i,m) cin >> a[i];
    rep(j,n) cin >> b[j];
    rep(i,m)rep(j,n)
      if(1 != __gcd(a[i],b[j]))
        G[i].pb(j);
    
    memset(match,-1,sizeof(match));
    int ans = 0;
    rep(i,m){
      memset(vis,0,sizeof(vis));
      ans += aug(i);
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 2316
#include <stdio.h>

int main()
{
	int N, K, X, Y;
	scanf("%d%d%d%d", &N, &K, &X, &Y);
	int i;
	int sum;
	for (i = 0, sum = 0; i < N; i++) {
		if (i < K) {
			sum += X;
		} else if (i >= K && i < N) {
			sum += Y;
		}
	}
	printf("%d\n", sum);
	return 0;
}


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

int main()
{
    string s,t;
    cin >> s >> t;
    long long a[t.size()][s.size()]={},sum[t.size()+1][s.size()+1]={};
    for(int j=0;j<(int)s.size();j++){
        if(t[0]==s[j]) a[0][j]=1;
            sum[0][j]+=a[0][j]%MOD;
    }
    for(int i=0;i<(int)t.size();i++){
        for(int j=0;j<(int)s.size();j++){
            if(t[i]==s[j]) a[i][j]=1;
                sum[i+1][j+1]=(sum[i+1][j]+sum[i][j]*a[i][j])%MOD;
        }
    }
    cout << sum[t.size()][s.size()] << endl;
    return 0;
}



Measured memory_bytes: 18840
/*************************************************************************
     File Name: B.cpp
     ID: obsoles1
     BLOG: blog.csdn.net/obsolescence
     LANG: C++ 
     Mail: 384099319@qq.com 
     Created Time: 日 10/ 2 13:48:09 2016
 ************************************************************************/
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();++it)
#define ABS(x,y) ((x)>(y)?((x)-(y)):((y)-(x)))
#define MEM0(x) memset(x,0,sizeof(x))
#define MEM1(x) memset(x,-1,sizeof(x))
#define MEMX(x) memset(x,0x3f,sizeof(x))
#define pb push_back
#include<iostream>
#include<algorithm>
#include<set>
#include<string>

using namespace std;
const int N=1e4+10;
set<string> my_set;
string ss[N];
int cnt[30];

int main() {
  int n,nn,k,i,j;
  string s;
  cin>>n>>k;
  for (i=j=0; i<n; ++i) {
    cin>>s;
    if (!my_set.count(s)) {
      my_set.insert(s);
      ss[j++]=s;
    }
  }
  n=j;
  for (i=0; i<n; ++i)
    cnt[ss[i][0]-'A']++;
  //cout<<"n="<<n<<endl;
  sort(cnt,cnt+26,greater<int>());
  int low=0,high=n/k,mid,ans;
  while (low<=high) {
    mid=(low+high)>>1;
    //cout<<"----mid="<<mid<<endl;
    int tmp=0,pre=0;
    for (i=0; i<26 && tmp<k; ++i) {
      if (cnt[i]+pre>=mid)
        tmp++,pre=MIN(mid,cnt[i])+pre-mid;
      else pre+=cnt[i];
      //cout<<"tmp="<<tmp<<endl;
    }
    if (tmp>=k) low=mid+1,ans=mid;
    else high=mid-1;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1920
#include <iostream>
#include <vector>
#include <algorithm>
#define FOR(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define REP(i, n) FOR(i, 0, n)
using namespace	std;

int n, m;

int solve(vector<int>& c, vector<int>& a) {
  vector<int> dp(m + 1, 0);
  FOR(i, 1, m + 1) REP(j, n)
    if(c[j] <= i)
      dp[i] = max(dp[i], dp[i - c[j]] + a[j]);
  return dp.back();
}

int main() {
  string name;
  while(cin >> n >> m) {
    vector<int>	c(n), v(n), d(n), l(n);
    REP(i, n) {
      cin.ignore(), getline(cin, name);
      cin >> c[i] >> v[i] >> d[i] >> l[i];
    }
    cout << max({solve(c, v), solve(c, d), solve(c, l)}) << endl;
  }
  return 0;
}



Measured memory_bytes: 3036