akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb emplace_back
#define mp make_pair
#define MOD 1000000007
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL))
int main()
{
     ll n;
     cin>>n;
     ll a[n];
     ll fre[3005]={0};
     for(ll i=0;i<n;i++)   cin>>a[i],fre[a[i]]++;
     sort(a,a+n);
     ll ans = 0;
     for(ll i=1;i<3005;i++)    fre[i] = fre[i] + fre[i-1];
     for(ll i=0;i<n;i++)
     {
         for(ll j=i+1;j<n;j++)
         {
             ll l = a[j] - a[i];
             ll r = a[j] + a[i];
             if(l<a[i] && r>a[i])    ans--;
             if(l<a[j] && r>a[j])    ans--;
             r = min(r,(ll)3004);
             ans += fre[r-1] - fre[l];
         }
     }
     cout<<ans/3;
}

Measured memory_bytes: 256
//おまじない
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#define INF 1e9+7
#define rep(i,m,n) for(int i=m;i<n;i++)
#define mrep(i,m,n) for(int i=m;i>n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない



int main() {

	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;

	rep(i, 0, ty - sy) {
		cout << 'U';
	}
	rep(i, 0, tx - sx) {
		cout << 'R';
	}
	cout << 'U';
	rep(i, 0, tx - sx + 1) {
		cout << 'L';
	}
	rep(i, 0, ty - sy + 1) {
		cout << 'D';
	}
	cout << 'R';
	//2
	rep(i, 0, tx - sx) {
		cout << 'R';
	}
	rep(i, 0, ty - sy) {
		cout << 'U';
	}
	cout << 'R';
	rep(i, 0, ty - sy + 1) {
		cout << 'D';
	}
	rep(i, 0, tx - sx + 1) {
		cout << 'L';
	}
	cout << 'U';

	
	return 0;
}


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

using namespace std;

// Header files, namespaces,
// macros as defined above
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>


#define f first
#define s second
#define db long double
#define pb push_back
#define sz(c) (c).size()
#define all(c) (c).begin(),(c).end()

typedef long long ll;
typedef pair <int , int> ii;
typedef pair <ii , int> iii;
typedef vector <int> vi;
typedef vector <ii> vii;
typedef vector <iii> viii;
typedef vector <vi> vvi;
typedef vector <vii> vvii;

const ll mod = 1e9+7;
const int MAX = 3e3+5;
const db eps = 1e-13;

ll memo[MAX][MAX] , v[MAX];


ll dp ( int lo , int hi ) {

    if( hi==lo )
        return v[lo];

    ll &res = memo[lo][hi];

    if( res != -1 )
        return res;

    return res = max( v[lo]-dp(lo+1,hi) , v[hi]-dp(lo,hi-1) );
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    cout<<setprecision(11)<<fixed;
    memset( memo , -1 , sizeof memo );
    int n;cin>>n;
    for( int i = 1; i <= n ; i++ ) {
        cin>>v[i];
        v[i];
    }

    cout<<dp( 1, n )<<"\n";

}



Measured memory_bytes: 71040
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  int n,d;
  cin>>n>>d;
  int div=2*d+1;
  int r = (n+div-1)/div;
  cout<<r<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mod 1000000007
int main()
{
    int n;
    cin>>n;
    lli arr[n];
    for(int i=0;i<n;i++) cin>>arr[i];
    vector<vector<lli>> dp(n,vector<lli>(n,LONG_MAX));
    lli ans=0;
    vector<lli> pre;
    for(int i=0;i<n;i++) pre.push_back(arr[i]);
    for(int i=1;i<n;i++) pre[i]+=pre[i-1];
    for(int len=1;len<=n;len++)
    {
        int j;
        lli mn=INT_MAX;
        for(int i=0;i<=n-len;i++)
        {
            j=i+len-1;
            if(i==j) dp[i][j]=0;
            else if(i+1==j){
                dp[i][j]=arr[i]+arr[j];
                if(mn>dp[i][j]) mn=dp[i][j];
            }
            else 
            {   lli cost=pre[j]-pre[i]+arr[i];
                for(int k=i;k<j;k++)
                {    
                     dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+cost);
                }  
            }   
        }
    }
    
    cout<<dp[0][n-1]<<endl;  
    return 0;
}

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

vector<int> par ; 

int root(int x) { //入力xの根を調べる
  if(par[x] ==x) return x ; 
  return par[x] = root(par[x]) ; 
}

void unite(int x , int y ) {//連結クエリの場合、xとyを連結
  int rx = root(x) ; 
  int ry = root(y) ; 
  
  if(rx == ry) return ; //もうすでに連結されてるよ〜？
  par[rx] = ry ;//まだ繋がってなかったよ！
}

bool same(int x , int y ){//入力x、yの根は同じかな？
  int rx = root(x) ; 
  int ry = root(y) ; 
  return rx == ry ; //同じならtrue
}

int main(){
  int N , M ; 
  cin >> N >> M ; 
  par.resize(N+1) ; 
  
  for(int i = 1 ; i <= N ; i++) par[i] = i ; //初期状態として頂点は全て自分自身が根
  
  for(int i = 0 ; i < M ; i++){
    int A , B ; 
    cin >> A >> B ; 
    if(A < B ) swap(B,A) ; 
    
    unite(A,B) ; //連結クエリ
  }
  vector<int> cnt(N+1) ; 
  for(int i = 1 ; i <= N ; i++){
    cnt.at(root(i))++;
  }
  
  sort(cnt.begin(),cnt.end());
  reverse(cnt.begin(),cnt.end());
  
  cout << cnt.at(0)<< endl ; 
  
  return 0 ; 
}

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

int main() {
  int n; cin >> n;
  char s[n]; for(int i = 0; i < n; ++i) cin >> s[i];
  for(int i = 0; i < n; ++i) {
    if(s[i] == 'Y') {
      cout << "Four" << endl;
      return 0;
    }
  }
  cout << "Three" << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        
        if(A == B){
            System.out.println( C );
        }else if(A == C){
            System.out.println( B );
        }else{
            System.out.println( A );
        }
    }
}


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

int main (){
	int a, b, c, d, x, y;
	
	cin >> a >> b >> c >> d;
	
	x = a*b;
	y = c*d;
	
	if (x>=y) cout << x << endl;
	else cout << y << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;
 
int main(){
    string s;
    cin >> s;

    if(s[2] == s[3]){
        if(s[4] == s[5]){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
    else {
        cout << "No" << endl;
    }
    return 0;
} 

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
public static void main(String[]srgs) {
	Scanner scan=new Scanner(System.in);
	int a=scan.nextInt();
	int b=scan.nextInt();
	String str[]=new String[a];
	boolean boolh[]=new boolean[a];
	boolean boolw[]=new boolean[b];
	for(int i=0;i<a;i++) {
		str[i]=scan.next();
	}
	for(int i=0;i<a;i++) {
		for(int j=0;j<b;j++) {
			if(str[i].charAt(j)=='#'){
				boolh[i]=true;
				boolw[j]=true;
			}
		}
	}
	for(int i=0;i<a;i++) {
		int count=0;
		for(int j=0;j<b;j++) {
			if(boolh[i]&&boolw[j]) {
				count=1;
				System.out.print(str[i].charAt(j));
			}
		}
		System.out.print(count==1?"\n":"");
	}
	scan.close();
}
}

Measured memory_bytes: 26168
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define endl '\n'
#define mem(i,j) memset(i,j,sizeof (i));
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define bit(s,i) (((s)>>(i))&1LL)
#define lowbit(x) ((x)&(-(x)))
#define siz(v) (long long)(v).size()
typedef int64_t ll;
typedef uint64_t ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
const int MAXN    = 2e5+9;
/*-----------------------------------------------------------------------------------------------------*/

signed main() {
	EmiliaMyWife

	int n, mx=0;
	cin >> n;
	string a;
	vector<string> ans;
	map<string, int> vt;
	for(int i = 0; i < n; i++) {
		cin >> a;
		vt[a]++;
		mx=max(mx, vt[a]);
	}
	for(auto x: vt) {
		if(x.S==mx) ans.pb(x.F);
	}
	sort(all(ans));
	for(auto x: ans) cout << x << endl;

	return 0;
}


Measured memory_bytes: 25584
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main() {
    ll x, y;
    cin >> x >> y;
    int ans = 0;

    while(x <= y) {
        ans++;
        x *= 2;
    }

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

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

void solution() {
    int n;
    cin >> n;
    map<string, int> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin>>s;
        m[s]++;
    }
    cout<<"AC x "<<m["AC"]<<'\n';
    cout<<"WA x "<<m["WA"]<<'\n';
    cout<<"TLE x "<<m["TLE"]<<'\n';
    cout<<"RE x "<<m["RE"]<<'\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
    int t;
    t=1;
    while(t--) solution();
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back 
#define fr first
#define sc second
#define Rep(i,n) for(int i=0;i<(n);i++)
#define All(v) v.begin(),v.end()
#define Uniq(v) v.erase(unique(All(v)),v.end())
typedef pair<int, int> Pii; 
typedef pair<int, Pii> Pip;
typedef pair<string, int> Psi;
const int INF = (1<<30);
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};

int main()
{
  int N, M, T;
  int a[10001];

  cin >> N >> M >> T;
  Rep(i, N) cin >> a[i];

  int ans = 0;
  int now = 0; //今の時間

  ans += a[0] - now - M;
  now = a[0];

  for(int i=1; i<N; i++) {
    if( a[i] - now > M * 2 ) {
      ans += a[i] - now - (M * 2);
      now = a[i];
    } else {
      now = a[i];
    }
  }

  ans += max(0, T - now - M);
  cout << ans << endl;
}

Measured memory_bytes: 3076
# include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
  // n - value
  cin >> n;
  int B[n-1];
	// B - array
  for(int i = 0; i < n-1; i++){
  	cin >> B[i];
  }
  int ans = B[0];
	// 
  for ( int i = 1; i < n-1; i++)
    ans += min(B[i-1], B[i]);
  // for last element
  ans += B[n-2];
  
  cout << ans << '\n';
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define pb push_back
#define MAXN 2000000
//typedef unsigned long long int ll
//typedef vector<ll> v;

vector<unsigned long long int>  A;



unsigned long long int n,aux;
unsigned long long int pibote = 1000000002;
unsigned long long int p = 0;
int main(){
	cin >> n;
	for(int i=0; i <n;i++){
		cin >> aux;
		A.pb(aux);
	}
	//cout << A[3] << '\n';
	//v.sort(v.begin(),v.end());
	//cout << v[n-1] - v[0] <<'\n';
	for(int i=0; i <n;i++){
		if(A[i] < pibote)
			pibote = A[i];
		
		if(A[i] > p)
			p=A[i];
	}
	cout << (p - pibote) << '\n';
	
	return 0;
}


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

#define ll long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//const int MOD = 1e9 + 7;
const int MAX = 1e5 + 1;

ll money = 1000;

void stockBuySell(int price[], int n)
{
	if (n == 1)
		return;

	int i = 0;
	while (i < n - 1)
	{
		while ((i < n - 1) && (price[i + 1] <= price[i]))
			i++;

		if (i == n - 1)
			break;

		int buy = i++;

		while ((i < n) && (price[i] >= price[i - 1]))
			i++;

		int sell = i - 1;

		//cout << "Buy on day: " << buy << "\t Sell on day: " << sell << endl;

		ll bought = money / price[buy];
		ll usedmoney = bought * price[buy];
		money -= usedmoney;
		ll sold = bought;
		ll earnedmoney = sold * price[sell];
		money += earnedmoney;
	}
}


int main()
{
	//IOS
	int t = 1;
	//cin >> t;
	while(t--)
	{
		int n;
		cin >> n;
		int a[n];
		for(int i = 0; i < n; ++i)
		{
			cin >> a[i];
		}
		stockBuySell(a, n);
		cout << money;
	}
	return 0;
}



Measured memory_bytes: 3496
INF = 10 ** 20

N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for coin in coin_list:
    for i in range(coin,N+1):
        dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

Measured memory_bytes: 6900
N, M = map(int, input().split())
X = [int(i) for i in input().split()]

X.sort()

if M == 1 or N >= M:
    print(0)
    exit()

length = []
for i in range(M-1):
    length.append([abs(X[i+1]-X[i]),i])

length.sort(key=lambda i:i[0], reverse=True)

cand = []
cand.append(0)
for i in range(N-1):
    cand.append(length[i][1]+1)
cand.append(len(X))

anslist = []
for i in range(len(cand)-1):
    anslist.append(X[cand[i+1]-1] - X[cand[i]])

ans = 0
for i in anslist:
    ans += i 

print(ans)


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

int main(void){
  int a=0,b=0,h=0,m=0;
  double rad=0.0;
  double ans=0.0;
  
  scanf("%d",&a);
  scanf("%d",&b);
  scanf("%d",&h);
  scanf("%d",&m);

  rad=h*30.0+(double)m*30.0/60.0;
  rad=(double)m*360.0/60.0-rad;
  rad=rad/180.0*3.141592653589793;
  
  ans=sqrt((a*a+b*b)-(2*a*b*cos(rad)));
  
  printf("%.9lf",ans);
}

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

using namespace std;
#define fordebug int hoge;cin>>hoge;
#define DEKAI 1000000007
#define INF (1<<28)
#define lp(i,n) for(int i=0;i<n;i++)
#define lps(i,j,n) for(int i=j;i<n;i++)
#define floot10 cout<<fixed<<setprecision(10);
#define int long long

typedef struct{
	int num;
	int right;
	int left;
	int dosetss(){
		num=-1;
		right=-1;
		left=-1;
	};
} nod2;

nod2 t[500000];
int used=1;
void Preorder(int now){
	cout<<" "<<t[now].num;
	if(t[now].left!=-1)Preorder(t[now].left);
	if(t[now].right!=-1)Preorder(t[now].right);
	return;
}
void Inorder(int now){
	if(t[now].left!=-1)Inorder(t[now].left);
	cout<<" "<<t[now].num;
	if(t[now].right!=-1)Inorder(t[now].right);
	return;
}

void insert(int now,int num){
	if(t[now].num==-1) t[now].num=num;
	else{
		if(t[now].num<num){
			if(t[now].right==-1){
				t[now].right=used;
				t[used].dosetss();
				used++;
			}
			insert(t[now].right,num);
		}
		else{
			if(t[now].left==-1){
				t[now].left=used;
				t[used].dosetss();
				used++;
			}
			insert(t[now].left,num);
		}
	}
	return;
}


signed main(){
	int n;
	cin>>n;
	t[0].dosetss();
	lp(i,n){
		string s;
		cin>>s;
		if(s[0]=='i'){
			int num;
			cin>>num;
			insert(0,num);
		}
		else{
			Inorder(0);
			cout<<endl;
			Preorder(0);
			cout<<endl;
		}
	}
	return 0;
}



Measured memory_bytes: 14720
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<stdio.h>
using namespace std;
int main(){
	int a,b,c;
	cin >> a >> b >> c;
	int count5 = 0;
	int count7 = 0;
	if (a == 5) count5++;
	if (b == 5) count5++;
	if (c == 5) count5++;
	if (a == 7) count7++;
	if (b == 7) count7++;
	if (c == 7) count7++;
	if(count5 == 2 && count7 == 1)
		cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

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

int main(){
  int a;
  cin >>a;
  
  for(int i=0;i<=(a/4) ;i++){
    for(int j=0;j<=(a/7);j++){
      if(a == 4*i+7*j){
       cout <<"Yes" << endl;
        
        return 0;
      }
    }
  }
  cout <<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), i##_max = (b); i < i##_max; ++i)
#define RFOR(i, a, b) for (int i = (b)-1, i##_min = (a); i >= i##_min; --i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define ALL(obj) (obj).begin(), (obj).end()

using namespace std;
using vi = vector<int>;
using vd = vector<double>;
using i64 = int64_t;

constexpr int INF = 1 << 30;
constexpr int MOD = 1000000007;

template <typename T>
void print(vector<T> &v) {
  REP(i, v.size()) {
    if (i) cout << " ";
    cout << v[i];
  }
  cout << endl;
}

constexpr int N = 100;
enum Color { White, Gray, Black };
vector<vi> M(N, vi(N, 0));
vi d(N), f(N), nt(N, 0);
vector<Color> color(N, White);

int next(int u) {
  FOR(v, nt[u], nt.size()) {
    nt[u] = v + 1;
    if (M[u][v]) return v;
  }
  return -1;
}

void dfs_visit(int r, int &tt) {
  fill(nt.begin(), nt.end(), 0);
  stack<int> S;
  S.push(r);
  color[r] = Gray;
  d[r] = ++tt;

  while (!S.empty()) {
    auto u = S.top();
    auto v = next(u);
    if (v != -1) {
      if (color[v] == White) {
        color[v] = Gray;
        d[v] = ++tt;
        S.push(v);
      }
    } else {
      S.pop();
      color[u] = Black;
      f[u] = ++tt;
    }
  }
}

void dfs(int n, int &tt) {
  REP(u, d.size()) {
    if (color[u] == White) dfs_visit(u, tt);
  }
  REP(i, d.size()) cout << i + 1 << " " << d[i] << " " << f[i] << endl;
}

int main() {
  int n, u, k, v;
  cin >> n;
  REP(i, n) {
    cin >> u >> k;
    REP(j, k) {
      cin >> v;
      M[u - 1][v - 1] = 1;
    }
  }
  int tt = 0;
  d.resize(n);
  f.resize(n);
  nt.resize(n);
  dfs(n, tt);
}


Measured memory_bytes: 3204
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define size 5000010
#define debug(x) cerr<<#x<<"="<<x
#define gc getchar()
#define db double
#define mod 998244353
#define ll long long
#define rep(i,s,n) for (register int i=s;i<=n;i++)
#define drep(i,n,s) for (register int i=n;i>=s;i--)
#define il inline
using namespace std;

il ll r()
{
    char c; ll x,f=1;
    for (c=gc;!isdigit(c);c=gc) if (c=='-') f=-1; x=c-'0';
    for (c=gc;isdigit(c);c=gc) x=(x<<1)+(x<<3)+c-'0';
    return f*x;
}
ll n,ans,res,X,a[20];

int main()
{
	n=r();
	rep(i,0,20)
	{
		a[i]=n%10,n/=10;
		X=i;
		if (!n) break;
	}
	for (int j=X;j>=0;j--)
	{
		if (a[j]==9) 
		{
			res+=9;
			ans=max(ans,a[j]-1+9*j);
		}
		else
		{
			res+=a[j]-1+j*9;bool f=1;
			if (j==X)
			{
				
				rep(k,0,X-1) if (a[k]!=9) f=0;
			}
			if (f) res++;
			ans=max(ans,res);
			break;
		}
	}
	ans=max(ans,res);
	cout<<ans; return 0;			
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

int mod = 1e9 + 7;

ll pow_mod(int x) {
  if (x == 0) {
    return 1;
  }
  ll y = pow_mod(x / 2);
  y = (y * y) % mod;
  if (x % 2 == 1) {
    y  = y * 2 % mod;
  }
  return y;
}

int main() {
  int n;
  scanf("%d", &n);
  vll a(n);
  rep (i, n) {
    scanf("%lld", &a[i]);
  }
  sort(all(a));
  if (n % 2 == 0) {
    rep (i, n) {
      int expect = i / 2 * 2 + 1;
      if (a[i] != expect) {
        printf("0\n");
        return 0;
      }
    }
    ll ans = pow_mod(n / 2);
    printf("%lld\n", ans);
    return 0;
  } else {
    if (a[0] != 0) {
      printf("0\n");
      return 0;
    }
    FOR (i, 1, n) {
      int expect = (i+1) / 2 * 2;
      if (a[i] != expect) {
        printf("0\n");
        return 0;
      }
    }
    ll ans = pow_mod(n / 2);
    printf("%lld\n", ans);
  }

  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,m;
  cin>>n;
  vector<string>v;
  for(int i=0;i<n;i++)
  {
      string s;
      cin>>s;
      v.push_back(s);
  }
sort(v.begin(),v.end());
string d=v[0];
int c=1;
cin>>m;
vector<string >r;
for(int i=0;i<m;i++)
{
   string t;
   cin>>t;
   r.push_back(t);
}
int l=0;
int k=0;
for(int i=1;i<v.size();i++)
{
    if(d==v[i])
    {
        c++;
    }
    else{
            for(int j=0;j<m;j++)
            {
                if(d==r[j])
                {
                    k++;
                }
            }
            l=max(l,(c-k));
            d=v[i];
            c=1;
            k=0;
    }
}

if(c>0)
{
    for(int i=0;i<m;i++)
    {
        if(d==r[i])
        {
            k++;
        }
    }
   l=max(l,(c-k));
}
cout<<l<<endl;
return 0;
}

Measured memory_bytes: 256
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    let l: i32 = buf[0..2].parse().unwrap();
    let r: i32 = buf[2..4].parse().unwrap();

    let lm = 1 <= l && l <= 12;
    let rm = 1 <= r && r <= 12;
    if lm && !rm {
        println!("MMYY");
    } else if !lm && rm {
        println!("YYMM");
    } else if lm && rm {
        println!("AMBIGUOUS");
    } else {
        println!("NA");
    }
}


Measured memory_bytes: 4352
while True:
    n = int(raw_input())
    if n == 0:
        break
    ap,bp = 0,0
    for _ in range(n):
        a,b = map(int, raw_input().split())
        if a > b:
            ap += a+b
        elif a < b:
            bp += a+b
        else:
            ap += a
            bp += b
    print ap, bp

Measured memory_bytes: 4464
/*
AizuOnline A2417
Title Flick
*/
#include <stdio.h>
#include <string.h>
char siin[]="kstnhmyrw";
char boin[]="aiueo";
char flick[]="TLURD";
char c1,c2;
char buf[1001];
//
main()
{
        int i,j;

        scanf("%s",&buf[0]);
        for(i=0;i<strlen(buf)/2;i++)
        {
                c1=buf[i*2];
                c2=buf[i*2+1];
                //printf("c1c2=%c%c\n",c1,c2);
                if(c1=='0' && c2=='U')
                {
                        printf("nn");
                        continue;
                }
                else if(c1=='0')
                {
                        printf("w");
                }
                else if(c1>'1')
                {
                        printf("%c",siin[c1-'2']);
                }
                for(j=0;j<5;j++)
                        if(c2==flick[j])
                                printf("%c",boin[j]);
        }
        printf("\n");
return(0);
}

Measured memory_bytes: 524
n, m = map(int, input().split())

a = list(map(int, input().split()))

a.sort(reverse=True)

b = 0
for i in a:
    b += i
c = b * (1 / (4 * m))

for j in range(m):
    if a[j] < c:
        print('No')
        exit()

print('Yes')

Measured memory_bytes: 3064
/*
confirm 0LL and 1LL
confirm cornercases such as 0
confirm times of cin < 10^6
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
using VecVec = vector<Vec>;
using Graph = vector<VecP>;
template <typename T>
using Vec1 = vector<T>;
template <typename T>
using Vec2 = vector<Vec1<T> >;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m)-1; (i) >= (n); --(i))
#define REPNR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
template <typename T>
bool chmax(T &a, const T& b){if(a < b){a = b; return true;} return false;}
template <typename T>
bool chmin(T &a, const T& b){if(a > b){a = b; return true;} return false;}
template <typename T>
void co(const T n){cout << n << endl;}
template <typename T>
void cosp(const T n){cout << n << ' ';}
template <typename T>
void coVec(const Vec &v){for(ll i : v) cosp(i); cout << endl;}
void sonic(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);}
void setp(const ll n){cout << fixed << setprecision(n);}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ld PI = acos(-1);
const ld EPS = 1e-11;

Graph tree;

bitset<50> dfs(ll node, ll e, bitset<50> bits){
	if(node == e) return bits;
	bitset<50> res(0);
	for(P i : tree[node]) if(!bits[i.sc]){
		bits.set(i.sc);
		res |= dfs(i.fs, e, bits);
		bits.reset(i.sc);
	}
	return res;
}

int main(void){
	ll n;
	cin >> n;
	tree.resize(n);
	VecP e(n);
	rep(i, n-1){
		ll a, b;
		cin >> a >> b;
		a--, b--;
		tree[a].pb({b, i});
		tree[b].pb({a, i});
		e[i] = {a, b};
	}
	ll m;
	cin >> m;
	VecP q(m);
	rep(i, m){
		ll u, v;
		cin >> u >> v;
		u--, v--;
		q[i] = {u, v};
	}

	Vec1<bitset<50> > edges(m);
	rep(i, m){
		edges[i] = dfs(q[i].fs, q[i].sc, 0);
	}

	ll ans = (1LL << (n-1));
	rep(bit, (1LL << m)){
		if(!bit) continue;
		bitset<20> bits(bit);
		ll cnt = bits.count();
		bitset<50> edge(0);
		rep(i, m) if(bits[i] == 1){
			edge |= edges[i];
		}
		ll pow = n-1-edge.count();
		if(cnt%2) ans -= (1LL << pow);
		else ans += (1LL << pow);
	}
	co(ans);

	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define MAX 1000000000000000000
#define mod 1000000007
#define sp fixed<<setprecision(12)
using namespace std;
ll a,b,c,d;
map<ll,ll> mp;
ll solve(ll n){
	if(n==0) return 0;
	if(n==1){
		return d;
	}
	if(mp.count(n)) return mp[n];
	ll l2=(n/2)*2;
	ll r2=((n+1)/2)*2;

	ll l3=(n/3)*3;
	ll r3=((n+2)/3)*3;

	ll l5=(n/5)*5;
	ll r5=((n+4)/5)*5;

	ll res=1e18;

	if(n<res/d) res=n*d;

	res=min(res,llabs(n-l2)*d+a+solve(l2/2));
	res=min(res,llabs(n-r2)*d+a+solve(r2/2));

	res=min(res,llabs(n-l3)*d+b+solve(l3/3));
	res=min(res,llabs(n-r3)*d+b+solve(r3/3));

	res=min(res,llabs(n-l5)*d+c+solve(l5/5));
	res=min(res,llabs(n-r5)*d+c+solve(r5/5));

	mp[n]=res;

	return res;
}
int main(){
	
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	//double	pi=3.14159265358979323846;

	int t;
	cin>>t;
	while(t--){
		mp.clear();
		ll n;
		cin>>n>>a>>b>>c>>d;
		ll ans=solve(n);
		cout<<ans<<endl;
	}

	
	
	return 0;
	
}

Measured memory_bytes: 4384
#include <iostream>
#include<cmath>
#include<iomanip>
using namespace std;

int main()
{
    double a,b,c;
    double p=3.1415926535;
    cin >> a >> b >> c;
    cout << fixed << setprecision(7) << a*b*sin(c*p/180)/2 << endl;
    cout << fixed << setprecision(7) << a+b+sqrt(pow(a,2)+pow(b,2)-2*a*b*cos(c*p/180)) << endl;
    cout << fixed << setprecision(7) << a*b*sin(c*p/180)/a << endl;
    return 0;
}



Measured memory_bytes: 3356
// https://atcoder.jp/contests/abc164/tasks/abc164_c
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    unordered_set<string> st;
    REP(i, N) {
        string t;
        cin >> t;
        st.insert(t);
    }
    cout << st.size() << endl;

    return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> list = {};
  for(int i=0; i<n; i++){
    int ai;
    cin >> ai;
    list.push_back(ai);
  }
  
  int count = 0;
  int num = 1;
  for(int j=0; j<list.size(); j++){
    if(list.at(j) != num) count++;
    else num++;
  }
  
  if(count == list.size()) count = -1;
  cout << count << endl;
  
  return 0;
}

Measured memory_bytes: 1400
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			if (n == 0)
				break;
			int sumA = 0;
			int sumB = 0;
			for (int i = 0; i < n; i++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				if (a > b)
					sumA += a + b;
				else if (a < b)
					sumB += a + b;
				else {
					sumA += a;
					sumB += b;
				}
			}
			System.out.println(sumA + " " + sumB);
		}

		sc.close();
	}
}

Measured memory_bytes: 58656
#include<stdio.h>

int main(void)
{
	int n,m,i,t;
	
	scanf("%d %d",&n,&m);
	
	int A[200][2000],B[2000],C[2000]={0};
	
	for(i=0;i<n;i++){
		for(t=0;t<m;t++){
			
			scanf("%d",&A[i][t]);
			
		}
	}
	for(i=0;i<m;i++){
		
		scanf("%d",&B[i]);
		
	}
	for(i=0;i<n;i++){
		for(t=0;t<m;t++){
			
			C[i]=C[i]+A[i][t]*B[t];
			
		}
		printf("%d\n",C[i]);
	}
	return 0;
}
	

Measured memory_bytes: 3188
# Contest No.: ABC168
# Problem No.: E
# Solver:      JEMINI
# Date:        20200517

import sys
import heapq

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a % b)

def main():
    modVal = 1000000007
    n = int(input())
    ppList = []
    pnList = []
    npList = []
    nnList = []
    znList = []
    nzList = []
    pzList = []
    zpList = []
    zzList = []
    numList = [0] * n
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        if a > 0 and b > 0:
            ppList.append((a, b))
        elif a > 0 and b < 0:
            pnList.append((a, b))
        elif a < 0 and b > 0:
            npList.append((a, b))
        elif a < 0 and b < 0:
            nnList.append((a, b))
        elif a == 0 and b < 0:
            znList.append((a, b))
        elif a < 0 and b == 0:
            nzList.append((a, b))
        elif a == 0 and b > 0:
            zpList.append((a, b))
        elif a > 0 and b == 0:
            pzList.append((a, b))
        else:
            zzList.append((a, b))
    ans = 1

    # zp, zn, pz, nz
    zAns = 2 ** (len(zpList) + len(znList)) % modVal + 2 ** (len(pzList) + len(nzList)) % modVal - 1
    zAns = zAns % modVal
    ans = zAns

    # pp, pn, np, nn
    ratioDict = {}
    for i in ppList:
        gcdVal = gcd(i[0], i[1])
        ratio = (i[0] // gcdVal, i[1] // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1
    for i in nnList:
        gcdVal = gcd(-i[0], -i[1])
        ratio = (-i[0] // gcdVal, -i[1] // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1

    for i in npList:
        gcdVal = gcd(abs(i[0]), abs(i[1]))
        ratio = (abs(i[1]) // gcdVal, abs(i[0]) // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in pnList:
        gcdVal = gcd(abs(i[0]), abs(i[1]))
        ratio = (abs(i[1]) // gcdVal, abs(i[0]) // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in ratioDict:
        temp = 2 ** ratioDict[i][0] % modVal
        temp += (2 ** ratioDict[i][1] - 1) % modVal
        ans *= temp
        ans = ans % modVal

    ans -= 1
    ans += len(zzList)
    ans = ans % modVal
    print(ans)
    return

if __name__ == "__main__":
    main()

Measured memory_bytes: 152956
#include<iostream>
#include<algorithm>
#include<vector>
using lint=int64_t;
using namespace std;

int main()
{
	int H,W;
	int a[510][510];
	
	cin >> H >> W;
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			cin >> a[i][j];
		}
	}
	
	vector<pair<int,int>> pv;
	vector<pair<int,int>> nt;
	for(int i=0;i<H;i++)
	{
		if(i%2==0)
		{
			for(int j=0;j<W;j++)
			{
				if(i==H-1 && j==W-1)
					break;
				if(a[i][j]%2==1)
				{
					pv.push_back(make_pair(i,j));
					a[i][j]--;
					if(j!=W-1)
					{
						nt.push_back(make_pair(i,j+1));
						a[i][j+1]++;
					}
					else
					{
						nt.push_back(make_pair(i+1,j));
						a[i+1][j]++;
					}
				}
			}
		}
		else
		{
			for(int j=W-1;j>=0;j--)
			{
				if(i==H-1 && j==0)
					break;
				if(a[i][j]%2==1)
				{
					pv.push_back(make_pair(i,j));
					a[i][j]--;
					if(j!=0)
					{
						nt.push_back(make_pair(i,j-1));
						a[i][j-1]++;
					}
					else
					{
						nt.push_back(make_pair(i+1,j));
						a[i+1][j]++;
					}
				}
			}
		}
	}
	
	cout << pv.size() << endl;
	auto pit=pv.begin();
	auto nit=nt.begin();
	for(;pit!=pv.end()&&nit!=nt.end();++pit,++nit)
		cout << pit->first+1 << " " << pit->second+1 << " " << nit->first+1 << " " << nit->second+1 << endl;
	
	return 0;
}

Measured memory_bytes: 5228
#include <iostream>

using namespace std;
typedef long long LL;

LL gcd(LL x, LL y){
  return (y == 0? x: gcd(y, x % y));
}

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

int main(){
  LL x, y;
  while(true){
	if(!(cin >> x >> y)) return 0;
	cout << gcd(x,y) << " " << lcm(x,y) << endl;
  }
  return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <limits>
#include <string>
#include <regex>
#include <cstdio>
#include <cstring>
#include <cmath>
#define INF 2000000000
#define REP(i,b,n) for(int i = (b); i < n; i++)
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int gcd(int a, int b){return b ? gcd(b, a % b): a;}
void yes(){cout<<"Yes"<<endl;return;}
void no(){cout<<"No"<<endl;return;}

int main()
{
    string s;
    cin >> s;
    if (s > "2019/04/30") cout << "TBD" << endl;
    else cout << "Heisei" << endl;
    return 0;
}


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

int main(void) {
    string w;
    cin>>w;
    map<char, int> mp;
    for (int i = 0; i < w.size(); i++) {
        char cur = w[i];
        if (mp.find(cur) != mp.end()) mp[cur] += 1;
        else mp[cur] = 1;
    }
    for (map<char, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
        if (it->second % 2 == 1) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
void tos(int a[]);
void ton(int a[]);
void toe(int a[]);
void tow(int a[]);

int main(void){
	int d[6],i;
	char o[101];
	for(i=0;i<6;i++){
		scanf("%d",&d[i]);
	}
	scanf("%s",o);
	for(i=0;o[i]!='\0';i++){
		if(o[i]=='S') tos(d);
		if(o[i]=='N') ton(d);
		if(o[i]=='E') toe(d);
		if(o[i]=='W') tow(d);
	}
	printf("%d\n",d[0]);
	return 0;
}

void tos(int a[]){
	int t=a[0];
	a[0]=a[4];
	a[4]=a[5];
	a[5]=a[1];
	a[1]=t;
}
void ton(int a[]){
	int t=a[0];
	a[0]=a[1];
	a[1]=a[5];
	a[5]=a[4];
	a[4]=t;
}
void toe(int a[]){
	int t=a[0];
	a[0]=a[3];
	a[3]=a[5];
	a[5]=a[2];
	a[2]=t;
}
void tow(int a[]){
	int t=a[0];
	a[0]=a[2];
	a[2]=a[5];
	a[5]=a[3];
	a[3]=t;
}



Measured memory_bytes: 2048
import sys
a=sys.stdin.readline()
res = [int(i) for i in a.split() if i.isdigit()] 
r,D,x2000 = [res[i] for i in (0,1,2)]
if (r>=2 and r<=5) and (D>=1 and D<=100) and (x2000>D and x2000<=200):
    x2001=r*x2000-D
    x2002=r*x2001-D
    x2003=r*x2002-D
    x2004=r*x2003-D
    x2005=r*x2004-D
    x2006=r*x2005-D
    x2007=r*x2006-D
    x2008=r*x2007-D
    x2009=r*x2008-D
    x2010=r*x2009-D
    print(x2001)
    print(x2002)
    print(x2003)
    print(x2004)
    print(x2005)
    print(x2006)
    print(x2007)
    print(x2008)
    print(x2009)
    print(x2010)
else:
    print("Error")

Measured memory_bytes: 3064
def fact(c)
    ret = 1
    
    for i in 2..c do
    	ret *= i
    end
    
    return ret
end

n, m, r = gets.split.map(&:to_i)

r = r - n * m
m = 0

if r < 0 then
	puts "0"
else
	p fact(n + r - 1) / fact(n - 1) / fact(r)
end

Measured memory_bytes: 82260
package main

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

func main() {
    x := nextInt()

    if x == 0 {
        fmt.Println(1)
    } else {
        fmt.Println(0)
    }
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
    bufsize := 1 * 1024 * 1024 // 1 MB
    var stdin = bufio.NewScanner(os.Stdin)
    stdin.Buffer(make([]byte, bufsize), bufsize)
    stdin.Split(bufio.ScanWords)
    return stdin
}

func nextString() string {
    stdin.Scan()
    return stdin.Text()
}

func nextBytes() []byte {
    stdin.Scan()
    return stdin.Bytes()
}

func nextInt() int {
    i, _ := strconv.Atoi(nextString())
    return i
}

func nextInt64() int64 {
    i, _ := strconv.ParseInt(nextString(), 10, 64)
    return i
}

func debug(args ...interface{}) {
    fmt.Fprintln(os.Stderr, args...)
}


Measured memory_bytes: 1804
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;//998244353;

template<class _T> static void getval(_T& a) {
	std::cin >> a;
}
template<class _T> static void getval(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void getval(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}

static void B();

int main()
{
	B();
	fflush(stdout);
	return 0;
}

static void B()
{
	int N;
	getval(N);

	std::string si;
	int ac, wa, tle, re;
	ac = wa = tle = re = 0;
	for (int i = 0; i < N; i++) {
		getval(si);

		if (si == "AC") {
			ac++;
		}
		else if (si == "WA") {
			wa++;
		}
		else if (si == "TLE") {
			tle++;
		}
		else if (si == "RE") {
			re++;
		}
	}
	
	printf("AC x %d\n", ac);
	printf("WA x %d\n", wa);
	printf("TLE x %d\n", tle);
	printf("RE x %d\n", re);
}


Measured memory_bytes: 3728
#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++ ){
				cout << "#" ;
			}
           cout << "\n";  
	     }
	     cout << endl;
		}

     return 0;
	
}

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

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

ll dp[104][100005];

int main() {
  ll n, ans = 0, W, vtot = 0, vmx = 0;
  cin >> n >> W;
  vector<ll> w(n), v(n);
  rep(i, n) cin >> w[i] >> v[i], vtot += v[i], vmx = max(vmx, v[i]);
  rep(i, 100005) dp[0][i] = INF;
  dp[0][0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= vmx * n; ++j) {
      if (j - v[i] >= 0)
        dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
      else
        dp[i + 1][j] = dp[i][j];
    }
  }

  rep(i, vmx * n + 1) if (dp[n][i] <= W) ans = i;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 80128
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>x>>y;
    if(x==0){
        if(y>=0)Cout(y);
        else Cout(y*-1+1);
    }
    else if(y==0){
        if(x>=0)Cout(x+1);
        else Cout(x*-1);
    } 
    else if(x>=0&&y>=0){
        if(x<=y)Cout(y-x);
        else{
            Cout(abs(x-y)+2);
        }
    }
    else if(x<=0&&y>=0){
        if(x*-1<=y)Cout(y-x*-1+1);
        else Cout(abs(y-x*-1)+1);
    }
    else if(y<=0&&x>=0){
        if(x<=y*-1)Cout(y*-1-x+1);
        else Cout(x-y*-1+1);
    }
    else{
        if(x<=y)Cout(x*-1-y*-1);
        else{
            Cout(y*-1-x*-1+2);
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <limits>
#include <set>
#include <vector>
#include <map>

using namespace std;

int main(){

    long long A;
    long long ret = 0;
    map<long long, int> M;
    long long B;
    long long C;
    
    int N;
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> A;
        M[i+A]++;
        ret += M[i-A];
    }
    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 26164
//
//  main.swift
//  TestSpace for AtCoder
//
//  Created by Koichi Okai on 2020/06/25.
//  Copyright © 2020 Koichi Okai. All rights reserved.
//

func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

func main() {
    let N = Int(readLine()!)!
    
    let a = readInts().sorted()
    
    let val = (1..<N).map { a[N-1 - $0/2] }.reduce(0) { $0 + $1 }

    print(val)
}

main()


Measured memory_bytes: 21216
N, M = map(int, input().split())
PY = [list(map(int, input().split())) + [i] for i in range(M)]

sortPY = sorted(PY, key=lambda x: x[1])
prefec = [0]*(N+1)
res = []
for p, y, i in sortPY:
    prefec[p] += 1
    strp = str(p)
    ID = '0'*(6-len(strp)) + strp + '0'*(6-len(str(prefec[p]))) + str(prefec[p])
    res.append([ID, i])

sortres = sorted(res, key=lambda x: x[1])
for i in range(M):
    print(sortres[i][0])


Measured memory_bytes: 48384
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using lint = long;
using llint = long long;
using namespace std;

void drawChessBoard(int H, int W) {
    rep(h, H) {
        rep(w, W) {
            if ((h + w) % 2 == 0)
                cout << "#";
            else
                cout << ".";
        }
        cout << endl;
    }
}

int main() {
    fastIO;

    int H, W;
    while (cin >> H >> W) {
        if (H == 0 && W == 0)
            break;
        drawChessBoard(H, W);
        cout << endl;
    }
}




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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 1, -1 , 0 , 0 };
int dy[] = { 0,  0,  1, -1 };

int main() {
	int n;
	cin >> n;
	vector<int> v(n), dp(10200,-1);
	for (int i = 0; i < n; i++)cin >> v[i];
	dp[0] = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 10000; j >= 0; j--) {
			if (dp[j] == 1) {
				dp[j + v[i]] = 1;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= 10000; i++) {
		
		if (i % 10 != 0 and dp[i] == 1) {
			ans = max(ans, i);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
N,_ = map(int, input().split())
A = [int(i) for i in input().split()]

INF = "-"

def chmax(a:str,b:str):
    if a == INF: return b
    elif len(a) < len(b): return b
    elif len(a) == len(a):
        if a < b: return b
    return a

# 数字 : 必要なマッチの本数
cnt = dict(zip(range(1,10), [2,5,5,4,5,6,3,7,6]))

# dp[i]: マッチをi本使って作れる数値の最大値
dp = [INF] * (10 ** 5)

# 初期条件
dp[0] = ""

# 配るDP
for i in range(N):
    if dp[i] == INF: continue
    for a in A:
        dp[i + cnt[a]] = chmax(dp[i + cnt[a]], dp[i] + chr(ord("0") + a))

print(dp[N])

Measured memory_bytes: 30836
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  
  int start = max(a,c);
  int end = min(b,d);
  
  cout << max(0,end-start) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;

int main(){
	int n, ans = 0;
	cin >> n;
	vector<int> num(n);
	for (int i = 0; i < n; i++)
		cin >> num[i];
	for (int i = 0; i < n; i += 2)
		if (num[i] % 2) ans += 1;
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 3596
#include<stdio.h>
void solve(int[], int[], int, int, int, int);
int P;
int main(){
  int n, q, i, j, cnt;
  int B[20], Pb[20];
  scanf("%d", &n);
  int A[n];
//  A = (int *)malloc(sizeof(int) * n);
  for(i = 0; i < n; i++)
    scanf("%d", &A[i]);
  scanf("%d", &q);
  int M[q];
  for(i = 0; i < q; i++){
    scanf("%d", &M[i]);
    P = 0;
    cnt = 0;
    for(j = 0; j < n; j++){
      if(A[j] <= M[i]){
	B[cnt] = A[j];
	Pb[cnt] = 0;
	cnt++;
      }
    }
    solve(B, Pb, 0, cnt, M[i], 0);
    if(P)
      printf("yes\n");
    else
      printf("no\n");
  }
//  free(A);
  return 0;
}

void solve(int B[], int Pb[], int j, int cnt, int M, int d){
  int i;
  for(i = j; i < cnt; i++){
    if(!Pb[i]){
      if(B[i] + d == M){
	P = 1;
	break;
      }
      else if(B[i] + d < M){
	Pb[i] = 1;
	solve(B, Pb, i, cnt, M, d + B[i]);
	Pb[i] = 0;
      }
    }
    if(P)
      break;
  }
}

Measured memory_bytes: 580
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k; cin >> k;
    vector<int> as(k);
    for(int i = 0; i < k; i++){
        cin >> as[i];
    }
    ll l = 0, r = 1e18;
    while(l + 1 < r){
        ll piv = (l + r) / 2, num = piv;
        for(int i = 0; i < k; i++){
            num = num / as[i] * as[i];
        }
        if(num == 2){
            l = piv;
        }else if(num < 2){
            l = piv + 1;
        }else{
            r = piv;
        }
        printd(l, r);
    }
    ll maxi = l;
    l = 0, r = maxi;
    while(l + 1 < r){
        ll piv = (l + r) / 2, num = piv;
        for(int i = 0; i < k; i++){
            num = num / as[i] * as[i];
        }
        if(num == 2){
            r = piv;
        }else{
            l = piv;
        }
        printd(l, r);
    }
    ll mini = r;
    ll mi2 = mini, ma2 = maxi;
    for(int i = 0; i < k; i++){
        mi2 = mi2 / as[i] * as[i];
        ma2 = ma2 / as[i] * as[i];
    }
    if(mi2 != 2 || ma2 != 2){
        cout << -1 << '\n';
    }else{
        cout << mini << ' ' << maxi << '\n';
    }
}


Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

bool isLower(char c){
	return ('a' <= c && c <= 'z');
}

int main(void){
	int n,i,cnt=0;
	bool flag = true;
	string s;
	cin >> s;
	n = s.l_ength();
	if(s[0]!='A' || !isLower(s[1]) || !isLower(s[n-1]) ){
		flag = false;
	}
	for(i=(n-2); i>1; --i){
		if(s[i] == 'C'){
			++cnt;
		}else if(!isLower(s[i])){
			flag = false;
		}
	}
	cout << (((cnt==1) && flag)?"AC":"WA") << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
  char buf[4];
  int a = 0;

  scanf("%s", buf);
  for(int i = 0; i < 4; i++) {
    if(buf[i] == '+') {
      a++;
    } else if(buf[i] == '-') {
      a--;
    }
  }
  printf("%d\n", a);
}


Measured memory_bytes: 128