akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(int i=(s);i<(t);++i)
#define per(i,s,t) for(int i=((t)-1);i>=s;--i)
#define repb(i,s,t) for(int i=(s);i<=(t);++i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)x.size())
#define mst(a,b) memset(a,b,sizeof(a))
#define mcpy(des,sor) memcpy(des,sor,sizeof(sor))
#define dd(x) cout<<#x<<'='<<x<<' '
#define de(x) cout<<#x<<'='<<x<<'\n'
#define fi first
#define se second
#define sq(x) ((x)*(x))
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;

const int inf = 0x3f3f3f3f;
const ll mod = 1e9+7;
const db eps = 1e-8;

char io[1<<15],*is=io,*ie=io+1;
#define rd if(++is==ie)ie=(is=io)+fread(io,1,sizeof(io),stdin)
template<class T>
inline bool Cin(T &a){
	a=0;bool s=0;
	if(is==ie)return 0;
	do{rd;if(*is=='-')s=1;}while(!isdigit(*is)&&is!=ie);
	if(is==ie)return 0;
	do{(a*=10)+=*is&15;rd;}while(isdigit(*is)&&is!=ie);
	if(s)a=-a;;return 1;}

inline int Gets(char a[]){
	int p=0;
	if(is==ie)return 0;
	do rd; while(!isgraph(*is)&&is!=ie);
	if(is==ie)return 0;
	do {a[p++]=*is;rd;}while(isgraph(*is)&&is!=ie);
	a[p]=0;return p;}

#define maxn 200005
ll x[maxn],s[maxn];

int main()
{
	mst(x,0);mst(s,0);
	int n,p;ll X,t,ans=~0ull>>1;
	Cin(n);Cin(X);
	repb(i,1,n)
	{
		Cin(x[i]);
		s[i]=s[i-1]+x[i];
	}
	for(int k=n;k>=1;--k)
	{
		t=0;p=n;
		repb(i,1,n/k+1)
		{
			if(i==1)t+=(s[max(p,0)]-s[max(0,p-k)])*5;
			else t+=(s[max(p,0)]-s[max(0,p-k)])*(2*i+1);
			p-=k;
			if(t>=ans)break;
		}
		ans=min(ans,X*(n+k)+t);
	}
	printf("%lld\n",ans);
}

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

using ll = long long;
using namespace std;
const int INFint = 1e9+1;
const ll INFll = (ll)1e18+1;
ll MOD=1e9+7;


int main(){
  string s;
  cin>>s;
  if(s == "RRS" || s == "SRR") cout << 2 << endl;
  else if (s == "RRR") cout << 3 << endl;
  else if (s == "SSS") cout << 0 << endl;
  else if(s == "RSR") cout << 1 << endl;
  else cout << 1 << endl;
  return 0;
}



Measured memory_bytes: 3556
#include<stdio.h>
#include<string.h>
int main(){
  int h,m,n,i,j,k,len;
  char work;
  char s[200];
  while(1){
    scanf("%s",s);
    len=strlen(s);
    if(s[0]=='-')break;
    scanf("%d",&m);
    for(i=0;i<m;i++){
      scanf("%d",&h);
      for(j=0;j<h;j++){
        work=s[0];
        for(k=0;k<len-1;k++){
          s[k]=s[k+1];
        }
        s[len-1]=work;
      }
    }
    printf("%s\n",s);
  }
  return 0;
}

Measured memory_bytes: 2608
#include<algorithm>//everybody dies in their nightmares
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<string>
#include<vector>
#include<sstream>
#include<cmath>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ff(i,a,b) for(register int i=a;i>=b;--i)
#define debug(x) cerr << #x << " : " << x << " " << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
const ll mod = 1e9 + 7;
const double tiaohe = 0.57721566490153286060651209;
ll oula(ll x) { ll res = x;f(i, 2, x / i) { if (x % i == 0) { res = res / i * (i - 1);while (x % i == 0) x /= i; } }if (x > 1) res = res / x * (x - 1);return res; }
ll quickmod(ll a, ll n, ll m) { ll s = 1;while (n) { if (n & 1) { s = s * a % m; }a = (a*a) % m;n = n / 2; }return s; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d) { if (!b) { d = a, x = 1, y = 0; } else { ex_gcd(b, a % b, y, x, d);y -= x * (a / b); } }
ll inv(ll t, ll p) { ll d, x, y;ex_gcd(t, p, x, y, d);return d == 1 ? (x % p + p) % p : -1; }
bool isPrime(ll x) { if (x == 2)return true;if (x % 2 == 0)return false;for (ll i = 2;i*i <= x;i++) if (x % i == 0)return false; return true; }
//double a = log(n) +tiaohe + 1.0 / (2 * n);
double eqa = (1 + sqrt(5.0)) / 2.0;

const int N = 6e5 + 5;
int t;
const double p = 3.1415926;
int a[N];
int main()
{
	int r;
	while (cin >> r)
	{
		printf("%.8lf", 2 * p*r);
	}
	return 0;
}

Measured memory_bytes: 3724
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vp;
const ll INF=99999999999999999;
ll a,b,c,d,e,f,ans=0;
int main(){
    cin>>a>>b>>c;
    if(a==b&&b==c)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;
#define MAX_N 100100

int dp[MAX_N];

int main(){
	int n;
	cin >> n;
	REP(i,MAX_N) dp[i] = INF;
	dp[0] = 0;
	for(int i = 1; i <= n; i++){
		dp[i] = min(dp[i], dp[i - 1] + 1);
		for(int j = 1; j <= i; j *= 6) dp[i] = min(dp[i], dp[i - j] + 1);
		for(int j = 1; j <= i; j *= 9) dp[i] = min(dp[i], dp[i - j] + 1);
	}
	cout << dp[n] << endl;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

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

void solve(int test_case) {
	int h,w;
	cin>>h>>w;
	vector<vector<char>> arr(h+2,vector<char>(w+2,'#'));
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)cin>>arr[i][j];
	for(auto a:arr){
		for(char b:a)cout<<b;
		cout<<"\n";
	}
}

int main() {
	
	////// FILE BASED IO////
	//freopen("in", "r", stdin);
	//freopen("out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
}	


Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#include <utility>
#include <tuple>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for (int i=0;i<n;i++)

ll mod = 1e9+7;

// 階乗
ll factorial(ll a){
    if (a==1){
        return 1;
    }
    return a * (factorial(a-1));
}

//組み合わせの数
ll nCr(ll n,ll r){
    return factorial(n)/(factorial(r)*factorial(n-r));
}

//重複する組み合わせの数
ll nHr(ll n,ll r){
    return factorial(n+r-1)/factorial(r);
}

int main(){
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i=0;i<n;i++){
        cin >> s[i];
        sort(s[i].begin(),s[i].end());
    }
    long ans = 0;
    map<string,ll> str;
    for (int i=0;i<n;i++){
        if (str[s[i]]!=0){
            str[s[i]]++;
        } else {
            str[s[i]] = 1;
        }
    }
    for (auto ss=str.begin();ss!=str.end();ss++){
        if (ss->second>1){
            ans += (ss->second*(ss->second-1))/2;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 18176
# -*- coding: utf-8 -*-
import sys

N = int(input())
C = input()

l = 0
r = len(C) - 1
ans = 0

while l < r:
    l = C.find('W', l)
    r = C.rfind('R', l, r + 1)
    #print('l = {}'.format(l))
    #print('r = {}'.format(r))
    if l == -1 or r == -1 or l > r:
        #print('kita')
        break

    l += 1
    r -= 1

    ans += 1

print(ans)


Measured memory_bytes: 9456
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,m,k;
    cin >> n >> m >> k;
    vi a(n),b(m);
    cin >> a >> b;
    vl sum(m+1,0);
    rep(i,m) sum[i+1] = sum[i]+b[i];
    int ans = 0;
    rep(i,m+1) if(sum[i] <= k) chmax(ans,i);
    ll now = 0;
    rep(i,n) {
        now += a[i];
        auto it = upper_bound(all(sum),k-now);
        if(it == sum.begin()) continue;
        it--;
        chmax(ans,i+1+int(it-sum.begin()));
    }
    cout << ans << endl;
}

Measured memory_bytes: 6368
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int a[5] = {0};
	rep (i, 5) cin >> a[i];
	int k; cin >> k;
	bool ok = true;
	rep (i, 5){
		for (int j = i + 1; j < 5; ++j){
			ok &= (a[j] - a[i] <= k);
		} // end for
	} // end rep

	cout << (ok ? "Yay!" : ":(") << endl;

	return 0;
}

Measured memory_bytes: 256
n=int(input())
arr=list(map(int,input().split()))
flag=[-1]*n
ans=[]
for i in range(n-1,-1,-1):
  cnt=0
  for j in range(i,n,i+1):
    if j==i:
      continue
    else:
      if flag[j]==1:
        cnt+=1
  if (arr[i]+cnt)%2==0:
    flag[i]=0
  else:
    flag[i]=1
    ans.append(i+1)
num=len(ans)
if num==0:
  print(0)
else:
  print(num)
  print(*ans)

Measured memory_bytes: 14096
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <sstream>

using namespace std;

int main(){
	
	int n;
	
	while(true){
		
		cin >> n;
		if(n == 0){
			break;
		}
		
		bool sche[100][100];
		
		for(int i = 0; i < 100; i++){
			for(int j = 0; j < 100; j++){
				sche[i][j] = false;
			}
		}
		
		long long int ALL = 0;
		
		for(int loop = 0; loop < n; loop++){
			ALL *= 2;
			ALL += 1;
		}
		
		long long int DP[100];
		
		long long int cur = 1;
		
		for(int i = 0; i < n; i++){
			DP[i] = cur;
			cur *= 2;
		}
		
		for(int i = 0; i < n; i++){
			int hoge;
			cin >> hoge;
			for(int j = 0; j < hoge; j++){
				int poyo;
				cin >> poyo;
				sche[i][poyo] = true;
			}
		}
		
		int ans = -1;
		
		for(int i = 0; i < 100; i++){
			for(int j = 0; j < n; j++){
				for(int k = j + 1; k < n; k++){
					if(sche[j][i] && sche[k][i]){
						DP[j] = DP[j] | DP[k];
						DP[k] = DP[j] | DP[k];
					}
				}
			}
			
			bool flag = false;
			
			for(int j = 1; j < n; j++){
				flag = flag || (DP[j] == ALL);
			}
			
			if(flag){
				ans = i;
				break;
			}
			
		}
		
		cout << ans << endl;
		
	}
	
	return 0;
}

Measured memory_bytes: 3080
/*  
    |\_/|
    |* *|
    \_+_/
*/
#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

int main(){

  cin.tie(0);     // cout と cin の同期を切る
  ios::sync_with_stdio(false);  /* cの stdioストリーム (printfとか)と*/



  int a,b,c,d;

  cin>>a>>b>>c>>d;

  if(a*b>=c*d){
    cout<<a*b<<endl;
  }else{
    cout<<c*d<<endl;
  }

  return 0;

}




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

main(){
	string a;
	cin >> a;
	bool flag=false;

	int i;
	for(i=0;i<a.length();i++){
		if(a[i]=='C'){
			break;
		}
	}
	for(;i<a.length();i++){
		if(a[i]=='F'){
			flag=true;
			break;
		}
	}
	if(flag==true){
		cout << "Yes" <<endl;
	}else{
		cout << "No" <<endl;
	}
}



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

template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar.size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}


int main(int argc, char const* argv[])
{
    int n;
    cin >> n;

    vector<vector<int> > board(2);
    board[0].resize(n);
    board[1].resize(n);

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }

    int m=0;
    for (int j = 0; j < n; j++) {
        int t=0;
        for (int k = 0; k < j+1; k++) {
            t += board[0][k];
        }
        for (int k = j; k < n; k++) {
            t += board[1][k];
        }
        m = max(m,t);
    }

    cout << m << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
int main(){
	int N; 
	cin >> N; 
	int A[100010] = {}; 
	for(int i = 1; i <= N; i++){
		cin >> A[i]; 
	}
	int count = 0; 
	for(int i = 1; i <= N; i++){
		if(A[A[i]] == i) count ++; 
	}
	cout << count / 2 << endl;
}

Measured memory_bytes: 640
//#include"bits/stdc++.h"
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
// using pAr = product_as_root;
const ll mod = 1e9+7;
ll n;
ll sn[200005];
ll pAr[200005];
vector<ll> G[200005];
ll qpow(ll x,ll n,ll mod)
{
	ll res =1;
	while(n>0)
	{
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
void dfs_sn(ll u,ll v){
	for(auto i:G[u]){
		if(i!=v){
			dfs_sn(i,u); sn[u]+=sn[i];
		}
	}
	sn[u]++;
}
void dfs_cr(ll u,ll v){
	for(auto i:G[u]){
		if(i!=v){
			pAr[i]=pAr[u]*qpow(sn[i],mod-2,mod)%mod*(n-sn[i])%mod;
			dfs_cr(i,u);
		}
	}
}
int main(){
	//freopen("input.txt","r",stdin);
	cin>>n;
	ll t1,t2;
	for(ll i=0;i<n-1;i++) {
		cin>>t1>>t2;
		G[t1].push_back(t2);
		G[t2].push_back(t1);
	}
	dfs_sn(1,0);
	//init
	pAr[1]=1;
	for(ll i=1;i<=n;i++) pAr[1]=pAr[1]*sn[i]%mod;
	dfs_cr(1,0);
	//factorial
	ll fac=1;
	for(ll i=2;i<=n;i++) fac=fac*i%mod;
	for(ll i=1;i<=n;i++){
		cout<<fac*qpow(pAr[i],mod-2,mod)%mod<<endl;
	}
	//for(int i=1;i<=8;i++) cout<<pAr[i]<<" ";
	return 0;
}




Measured memory_bytes: 18688
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[4];
        for (int i = 0 ; i < 4 ; i++) {
            a[i] = n % 10;
            n /= 10;
        }
//        if (a[0] == a[3]) {
//            System.out.println("No");
//            return;
//        }
        if ((a[0] == a[1] && a[1] == a[2]) || (a[1]==a[2] && a[2] == a[3])) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }


    }

}


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

 int main() {
 int A, B, C, K, cnt = 0;
 cin >> A >> B >> C >> K;
 while (A >= B) { cnt += 1; B *= 2; }
 while (B >= C) { cnt += 1; C *= 2; }
 if (cnt <= K) cout << "Yes" << endl;
else cout << "No" << endl;
	return 0;
 }


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

const int C = (int)1e5 + 1;
int N, M, K;
vector<int> parent(C, -1);
vector<vector<int>> graph(C);
vector<vector<int>> block(C);

int root(int num) {
    return parent[num] == -1 ? num : parent[num] = root(parent[num]);
}

void merge(int a, int b) {
    int p1 = root(a);
    int p2 = root(b);
    if (p1 == p2) return;
    if (p1 < p2) parent[p2] = p1;
    else parent[p1] = p2;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(10);
    
    cin >> N >> M >> K;
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        merge(a, b);
    }
    for (int i = 0; i < K; ++i) {
        int c, d;
        cin >> c >> d;
        block[c].push_back(d);
        block[d].push_back(c);
    }
    int cnt[N + 1]; fill(cnt, cnt + N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        int p = root(i);
        ++cnt[p];
        //cout << "[i=" << i << ", p=" << p << "], ";
    }
    for (int i = 1; i <= N; ++i) {
        int p1 = root(i);
        int count = cnt[p1] - graph[i].size() - 1; // Friends + myself from union
        for (int b : block[i]) {
            int p2 = root(b);
            if (p1 == p2) count--;
        }
        cout << count << " ";
    }
    cout << endl;
}   


Measured memory_bytes: 12664
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
ll a[200005];
int cmp(ll A,ll B)
{
	return A<B;
}
int n;
ll cha(ll x)
{
	ll ans=0;
//	printf("#################################%d\n",n);
	for(int i=1;i<n;i++)
	{
		int ls=i+1;
		int rs=n;
		if(a[i]>0)
		{
			while(ls!=rs)
			{
				int ms=(ls+rs)/2;
				if(a[ms]*a[i]<x)
				{
					ls=ms+1;
				}
				else
				{
					rs=ms;
				}
			}
			if(a[i]*a[n]<x)
			{
				ls++;
			}
			ls--;
			ans+=(ls-i);
		}
	//	printf("**1:%lld\n",ans);
		if(a[i]==0)
		{
			if(x>0)
			{
				ans+=(n-i);
			}
		}
	//	printf("**2:%lld\n",ans);
		if(a[i]<0)
		{
	//		printf("<<<<<<<<<<<<<<\n");
			while(ls!=rs)
			{
				int ms=(ls+rs)/2;
	//			printf("$$%d$$%d$$%d$$\n",ls,ms,rs);
				if(a[ms]*a[i]<x)
				{
					rs=ms;
				}
				else
				{
					ls=ms+1;
				}
			}
			if(a[i]*a[n]>=x)
			{
				ls++;
			}
			ls--;
			ans+=(n-ls);
		}
	//	printf("**3:%d\n",ans);	
	//	printf("****%lld\n",x);
	}
	return ans;
}
int main()
{
	ll m;
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+n+1,cmp);
//	for(int i=1;i<=n;i++)
//	{
//		printf("%lld\n",a[i]);
//	}
//	printf("********\n");
	ll l=-inf;
	ll r=inf;
	while(l!=r)
	{
		ll mid=(l+r)>>1;
//		printf("%lld***%lld***%lld\n",l,r,mid);
		if(cha(mid)>=m)
		{
			r=mid;
		}
		else
		{
			l=mid+1;
		}
	}
	printf("%lld\n",l-1);
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define bitsz(x) int(__builtin_popcount(x))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
#define mod 1000000007
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

 
int main() {
    int n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    ll ans = 0;
    vector<ll> sum(n+1,0);
    rep(i,n) {
        sum[i+1] = sum[i] + a[i];
    }
    for (int i=0; i<=n-2; i++) {
        ll tmp = (sum[n]-sum[i+1])%mod*a[i];
        tmp %= mod;
        ans += tmp;
        ans %= mod;

    }
    cout << ans << endl;
}


Measured memory_bytes: 6424
n = int(input())
li =[list(map(int, input().split())) for _ in range(2)]
count_li = [[0 for _ in range(n)] for _ in range(2)]
count= 0
for i in range(n):
    count += li[0][i]
    count_li[0][i] = count
    if i > 0:
        count_li[1][i] = max(count_li[1][i-1], count_li[0][i])+li[1][i]
    else:
        count_li[1][i] = li[0][i]+li[1][i]

print(count_li[1][n-1])
    

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

int main() {
  int N,K;
  cin >> N >> K;

  vector<int> h;

  for (int i = 0; i < N; ++i) {
    int a;
    cin >> a;
    h.push_back(a);
  }

  int c = 0;
  
  for (int i = 0; i < N; i++) {
    if ( h[i] >= K ) {
      c++;
    }
  }
  
  cout << c;
}
  

Measured memory_bytes: 892
class Dice():

    def __init__(self):
        self.number = [i for i in range(6)]
        self.work = [i for i in range(6)]
        self.order = 'NNNNWNNNWNNNENNNENNNWNNN'

    def setNumber(self,n0,n1,n2,n3,n4,n5):
        self.number[0] = n0
        self.number[1] = n1
        self.number[2] = n2
        self.number[3] = n3
        self.number[4] = n4
        self.number[5] = n5


    def roll(self,loc):
        for i in range(6):
            self.work[i] = self.number[i]

        if loc == 'E':
            self.setNumber(self.work[3],self.work[1],self.work[0],self.work[5],self.work[4],self.work[2])
        elif loc == 'N':
            self.setNumber(self.work[1],self.work[5],self.work[2],self.work[3],self.work[0],self.work[4])
        elif loc == 'S':
            self.setNumber(self.work[4],self.work[0],self.work[2],self.work[3],self.work[5],self.work[1])
        elif loc == 'W':
            self.setNumber(self.work[2],self.work[1],self.work[5],self.work[0],self.work[4],self.work[3])


    def equals(self,another):

        ret = False;

        for i in range(len(self.order)):
            self.roll(self.order[i])
            FLG = True
            for k in range(6):
                if self.number[k] != another.number[k]:
                    FLG = False
                    break
            if FLG == True:
                return True

        return ret



num_dice = int(input())
DICE = []

for i in range(num_dice):
    table = list(map(int,input().split()))
    tmp_dice = Dice()
    tmp_dice.setNumber(table[0], table[1], table[2], table[3], table[4], table[5])
    DICE.append(tmp_dice)

FLG = True

for i in range(num_dice-1):
    for k in range(i+1,num_dice):
        if DICE[i].equals(DICE[k]) == True:
            FLG = False
            break


if FLG == True:
    print("Yes")
else:
    print("No")



Measured memory_bytes: 5624
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    ll n, m;
    cin >> n >> m;

    ll sum = 0;
    rep(i, m) {
        ll a;
        cin >> a;
        sum += a;
    }

    if(sum > n) {
        out(-1);
    }
    else {
        out(n - sum);
    }

    re0;
}

Measured memory_bytes: 3636
N, M, C = map(int, input().split())
b = [i for i in map(int, input().split())]
A = [0]*N
for i in range(N):
    A[i] = [i for i in map(int, input().split())]

count = 0 
for r in range(N):
    tmp = 0 
    for c in range(M):
        tmp += A[r][c] * b[c]
    tmp += C
    if tmp > 0: count += 1                                                                                     
    
print(count)

Measured memory_bytes: 3064
class PrintAChessboard:
    def output(self, H, W):
        s1 = ""
        s2 = ""
        for w in range(W):
            if w % 2 == 0:
                s1 += "#"
                s2 += "."
            else:
                s1 += "."
                s2 += "#"
        for h in range(H):
            if h % 2 == 0:
                print s1
            else:
                print s2
        print

if __name__ == "__main__":
    pc = PrintAChessboard()
    while True:
        h, w = map(int, raw_input().split())
        if h == 0 and w == 0:
            break
        pc.output(h, w)

Measured memory_bytes: 6400
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
        //MyDebugger.Test(process, "../TextFile2.txt");
        //MyDebugger.MakeTestCase("../TextFile2.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var spl   = input.ReadLine().Split(' ');
        var n     = int.Parse(spl[0]);
        var x     = int.Parse(spl[1]);

        var xx = ToIntArray(input.ReadLine(), n);

        var yy = new int[n];
        for(int i=0; i<n; i++) {
            yy[i] = Math.Abs(xx[i] - x);
        }

        var min = yy.Min();

        for (int j=1; true; j++) {
            if (min % j != 0) continue;
            var d = min / j;
            if (Check(yy, d)) return d;
        }
    }

    static bool Check(int[] yy, int d) {
        foreach(var y in yy) {
            if (y % d != 0) return false;
        }
        return true;
    }

    

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}

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


int main() {
    int n,m,a,b;
    vector<pair<int,int>> p;
    priority_queue<int> q;
    cin >> n >> m;
    for (int i=0;i<n;i++) {
        cin >> a >> b;
        p.push_back(make_pair(a,b));
    }
    sort(p.begin(),p.end());
    auto itr=p.begin();
    ll ans=0;
    for (int i=1;i<=m;i++) {
        while ((*itr).first<=i && itr!=p.end()) {
            q.push((*itr).second);
            itr++;
        }
        if (!q.empty()) {
            ans+=q.top();
            q.pop();
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1908
n,r  = map (int, raw_input().split(" "))
while (n,r) != (0,0) :
	deck = [n - i for i in range(n)]
	for i in range(r):
		p,c  = map (int, raw_input().split(" "))
		deck = deck[p-1:p-1+c] + deck[:p-1] + deck[p-1+c:]
	print deck[0]
	n,r  = map (int, raw_input().split(" "))

Measured memory_bytes: 4220
N,K = map(int, input().split())
probability = 0


for x in range(1,N+1):
    bekicount = 0
    y = x
    while y < K:
        y = y*2
        bekicount = bekicount +1
    probability = probability + (1/N)*(pow(0.5,bekicount))
    bekicount = 0
print(probability)

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

int main() {
	int N, A[3001];
	cin >> N;
	int result = 0;
	repeat(i, N) {
		cin >> A[i];
		result += A[i] - 1;
	}
	cout << result << endl;
	return 0;
}

Measured memory_bytes: 256
#pragma region Header
#ifdef DEBUG
#include "debug.hpp"
#else
#define NDEBUG
#define debug(...)
#define IFD(...)
#endif
#include <utility>
#include <cstdint>
#include <cmath>
#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <functional>
#include <algorithm>
#include <numeric>
#include <stdexcept>
#include <iostream>
#include <iomanip>
using namespace std;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
#define rep(i, n) for (int i = 0; i < static_cast<int>(n); ++i)
#define repd(i, n) for (int i = static_cast<int>(n) - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = static_cast<int>(a); i <= static_cast<int>(b); ++i)
#define FORD(i, b, a) for (int i = static_cast<int>(b); i >= static_cast<int>(a); --i)
template <typename T>
int SZ(T const &x)
{
    return static_cast<int>(x.size());
}
template <class T>
bool chmax(T &a, T const &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, T const &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}
#pragma endregion

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int n;
    cin >> n;
    vector a_s(n, 0);
    rep(i, n)
    {
        cin >> a_s[i];
    }

    int g = accumulate(a_s.begin(), a_s.end(), 0, [](int acc, int x) { return gcd(acc, x); });

    set<int> p_s;
    auto ins = [&](int p) {
        if (p_s.find(p) != p_s.end())
        {
            return false;
        }
        p_s.insert(p);
        return true;
    };
    bool flag = true;
    for (auto a : a_s)
    {
        for (int p = 2; p * p <= a; ++p)
        {
            if (a % p == 0)
            {
                if (not ins(p))
                {
                    flag = false;
                }
                while (a % p == 0)
                {
                    a /= p;
                }
            }
        }
        if (a != 1)
        {
            if (not ins(a))
            {
                flag = false;
            }
        }
    }

    cout << (flag ? "pairwise coprime" : (g == 1 ? "setwise coprime" : "not coprime")) << endl;

    return 0;
}


Measured memory_bytes: 10684
A = []
5.times{
  a = gets.to_i
  A << [a, a + ((a % 10) == 0 ? 0 : 10 - (a % 10))]
}

A.sort_by!{|a, t| t - a}

puts A[0, 4].inject(0){|r, (a, t)| r + t} + A[4][0]


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
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; }
const ll MOD = 1e9+7;

ll A[200][200];

int main(){
    ll N, K;
    cin >> N >> K;
    vector<ll> sn(N);
    REP(i,K){
        ll d;
        cin >> d;
        REP(t,d){
            ll a;
            cin >> a;
            a--;
            sn[a]++;
        }
    }

    ll ans = 0;
    REP(i,N){
        if(sn[i] == 0)
            ans++;
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 3600
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, A = MAP()
print(H//A+1 if H%A != 0 else H//A)

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

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

using namespace std;

const ll INF = 1LL<<60;

int main(){
  ll h,n;cin>>h>>n;
  vector<pair<ll,ll>> m(n);
  rep(i,n){
    ll a,b;cin>>a>>b;
    m[i]=make_pair(a,b);
  }

  vector<vector<ll>> dp(n+1, vector<long long>(h+1, INF));
  dp[0][0]=0;
  rep(i, n){
    rep(j, h+1){
      dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
      dp[i+1][min(j+m[i].first, h)] = min( dp[i+1][min(j+m[i].first, h)], dp[i+1][j]+m[i].second );
    }
  }

  cout<<dp[n][h];

  return 0;
}


Measured memory_bytes: 78592
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <deque>
#include <unordered_set>
#include <set>
#include <algorithm>

#define ll long long

using namespace std;

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

  int n , w;
  cin>>n>>w;
  vector<ll> dp(w+1, 0);
  ll W[n],o[n];
  for(int i = 0; i < n;++i){
    cin>>W[i]>>o[i];
  }
  for(int j = 0; j < n; ++j){
    for(int i = w; i-W[j] >= 0; --i){
      dp[i] = max((dp[i-W[j]]+o[j]), dp[i]);
    }
  }
  cout<<dp.back()<<"\n";
  
}


Measured memory_bytes: 1024
import sys

sr = lambda: sys.stdin.readline().rstrip()
lr = lambda: list(map(int, sr().split()))

h, w = lr()
alp = [0] * 26
for i in range(h):
        for c in sr(): alp[ord(c)-ord('a')] += 1

m2 = (h * (w%2) + w * (h%2)) // 2
one = h%2 and w%2
cant = False
for i in alp:
        if i%4!=0:
                if i%4==3:
                        if m2: m2 -= 1
                        else: cant = True
                        if one: one = False
                        else: cant = True
                if i%4==2:
                        if m2: m2 -= 1
                        else: cant = True
                if i%4==1:
                        if one: one = False
                        else: cant = True
print("YNeos"[cant::2])


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#ifdef dbg
#include "./printer.hpp"
#else
#define dump(x) void(0)
#endif

using namespace std;
#define ll long long
inline long  toInt(string s) {long  v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

int main(){
  ios_base::sync_with_stdio(0);

  ll n, q;
  cin >> n >> q;

  ll power = 1;
  ll sizepower;
  for(ll i = 1;;i++){
    power *= 2;
    if(n <= power){
      sizepower = i;
      break;
    }
  }

  vector<ll> d (1 << sizepower + 1, 0);
  
  for(ll i = 0; i < q; i++){
    ll t,x,y;
    cin >> t >> x >> y;
    if(t == 0){
      while(1){
	d[x] += y;
	if(x == 1 << sizepower){
	  break;
	}
	x = x + ((-x) & x);
      }
    }else{
      ll ans = 0;
      x--;
      while(1){
	if(x == 0){
	  break;
	}
	ans += d[x];
	x = x - (x & (-x));
      }
      ans *= -1;
      while(1){
	if(y == 0){
	  break;
	}
	ans += d[y];
	y = y - (y & (-y));
      }
      cout << ans << '\n';
    }

  }

}

Measured memory_bytes: 4944
import std.stdio, std.conv, std.string, std.range, std.algorithm, std.array,
  std.functional, std.container, std.typecons;

void main() {
  int N = readln.chomp.to!int;
  int[] A = readln.split.to!(int[]);
  int[] B = new int[N];

  B[0] = A.sum - 2 * iota(1, N-1, 2).map!(i => A[i]).sum;
  foreach(i; 1..N) {
    B[i] = 2*A[i-1] - B[i-1];
  }

  foreach(b; B) {
    write(b, " ");
  }
}


Measured memory_bytes: 5448
def main():
    N = int(input())
    work = []
    for _ in range(N):
        a, b, c = map(int, input().split())
        work.append((a,b,c))
    
    dp = [[0] * 3 for _ in range(N)]
    for i in range(N):
        for j in range(3):
            if i == 0:
                dp[i][j] = work[i][j]
                continue
            if j == 0:
                dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + work[i][0]
            elif j == 1:
                dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + work[i][1]
            elif j == 2:
                dp[i][2] = max(dp[i-1][1], dp[i-1][0]) + work[i][2]

    print(max(dp[N-1]))
    

if __name__ == "__main__":
    main()

Measured memory_bytes: 75608
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef long long ll;
typedef long long integer;
//////////////////////////////////////////////////
struct SegmentTree{
    // for vertex n
    // par (n-1)/2
    // chi 2n+1,2n+2

    // index i
    // bottom vertex n+i-1

    int segn2; // imply actually vertex number
    vector<int> data; 
     
    SegmentTree(int n){
        segn2=1;
        while(segn2<n) segn2*=2; //必要分2^Mを取る
         
        data.assign(segn2*2,0); // 2^31 - 1
    }
    
    // min [x,y]
    // save as [x,y)
    int query(int a,int b,int l=0,int r=-1,int k=0){
         
        if(r==-1) r+=segn2; // when calling function at first
         
        if(a<=l && r<=b) return data[k];
        if(r<a || b<l) return 0; 
        
        int vl = query(a,b,l,(l+r)/2,k*2+1);
        int vr = query(a,b,(l+r)/2+1,r,k*2+2);
        return vl+vr;
    }
     
    // i value |-> x (0-indexed)
    void update(int k,int x){
        k += segn2 - 1;
        data[k] += x;
         
        while(k > 0){
            k=(k-1)/2; //move to par
            data[k]=(data[k*2+1]+data[k*2+2]);
        }
         
        return;
    }
};

int main(){
    int N,q;
    SCD2(N,q);
    SegmentTree seg(N);

    REP(i,q){
        int com,x,y;
        SCD3(com,x,y);
        if (com == 0){
            x--;
            seg.update(x,y);
        }else{
            x--; y--;
            PRINTD(seg.query(x,y));
        }
    }
}



Measured memory_bytes: 3900
# -*- coding: utf-8 -*-

# スペース区切りの文字列の入力
st = input().split()
#商
div = int(st[0]) // (int(st[1]) + int(st[2]))
#余り
rem = int(st[0]) % (int(st[1]) + int(st[2]))

if(rem < int(st[1])):
  print(div * int(st[1]) + rem)
else:
  print(div * int(st[1]) + int(st[1]))
  

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include <iomanip>
#include<cmath>
#include<stdio.h>
#include<map>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
#define sort(s) sort(s.begin(),s.end())
#define r(s) reverse(s.begin(),s.end())
#define please return
constexpr auto AC = 0;
using namespace std;
int main() {
	int a,b;
	double s=0;
	cin >> a >> b;
	for (int i = 1; i <= a; i++) {
		double n = 1;
		for (int j = i;; j *= 2) {
			if (j >= b)break;
			n *= 0.5;
		}
		s += n;
	}
	s /= a;
	
	cout << fixed << setprecision(12) << s << endl;


		please AC;
}

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

int main(int argc, char *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll A, B, C;
    cin >> A >> B >> C;

    if (A+B+1 >= C) {
        cout << B+C << endl;
    } else {
        cout << A+2*B+1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pii pair <int,int>
#define pll pair <ll,ll>
#define testcase() int t; cin>>t; while(t--)
#define forn(i,n) for(int i=0;i<n;i++)
#define forn1(i,n) for(int i=1;i<=n;i++)
#define vll vector <ll>
#define all(v) v.begin(),v.end()

ll M = 1e9 + 7;
double pi = acos(-1.0);
ll powerm(ll x,ll y){ ll res=1; while(y){ if(y&1) res=(res*x)%M; y=y>>1; x=(x*x)%M;} return res%M; }
ll power(ll x,ll y){ ll res=1; while(y){ if(y&1) res=(res*x); y=y>>1; x=(x*x);} return res; }
ll max3(ll a,ll b,ll c){ return max( max(a,b),c ); }
ll gcd(ll a,ll b){if(b>a)return gcd(b,a); if(b==0)return a; return gcd(b,a%b);}
ll dp[101][100005];
	
int main() {
	
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	
	int n,w; cin>>n>>w;
	ll a[n+1],b[n+1];
	forn1(i,n) cin>>a[i]>>b[i];
	
	forn(i,n+1) forn1(j,100004) dp[i][j] = 1e18;
	
	forn1(i,n)
	{
	    forn1(j,100004)
	    {
	        dp[i][j] = dp[i-1][j];
	        if(b[i]<=j)
	        {
	            dp[i][j] = min( dp[i][j] , dp[i-1][j-b[i]] + a[i] );
	        }
	       // if(j<w+1)
	       //     cout<<i<<' '<<j<<' '<<dp[i][j]<<endl;
	    }
	}
	for(int i=100004;i>=1;i--)
	{
	    if(dp[n][i]==0) continue;
	    if(dp[n][i]<=w){ cout<<i; return 0; }
	}
	cout<<0;
	return 0;
}


Measured memory_bytes: 79232
#include <cstring>
#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int col[2*n], val[2*n];
    int pos[2][n];
    for (int i = 0; i < 2*n; i++) {
        char c; int a; cin >> c >> a;
        col[i] = c == 'B';
        val[i] = a-1;
        pos[c == 'B'][a-1] = i;
    }

    int cost[2][n+1][2*n];
    for (int c = 0; c < 2; c++) 
        for (int v = 0; v <= n; v++) {
            cost[c][v][0] = 0;
            for (int j = 1; j < 2*n; j++)
                cost[c][v][j] = cost[c][v][j-1] + int(col[j-1] == c && val[j-1] >= v);
        }

    int dp[n+1][n+1];
    memset(dp, 0, sizeof dp);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 && j == 0) { dp[0][0] = 0; continue; }
            int val = 1<<30;
            if (i > 0) {
                const int p = pos[0][i-1];
                val = min(val, dp[i-1][j] + cost[0][i][p] + cost[1][j][p]);
            }
            if (j > 0) {
                const int q = pos[1][j-1];
                val = min(val, dp[i][j-1] + cost[0][i][q] + cost[1][j][q]);
            }
            dp[i][j] = val;
        }
    }
    cout << dp[n][n] << endl;
}


Measured memory_bytes: 78464
/*
				   _ooOoo_
				  o8888888o
				  88" . "88
				  (| -_- |)
				  O\  =  /O
			   ____/`---'\____
			 .'  \\|     |//  `.
		    /  \\|||  :  |||//  \
		   /  _||||| -:- |||||-  \
		   |   | \\\  -  /// |   |
		   | \_|  ''\---/''  |   |
		   \  .-\__  `-`  ___/-. /
		 ___`. .'  /--.--\  `. . __
	  ."" '<  `.___\_<|>_/___.'  >'"".
	 | | :  `- \`.;`\ _ /`;.`/ - ` : | |
	 \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
				   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
		fozubaoyou    pass System Test!
		quoted from "https://codeforces.com/contest/472/submission/7996840"
*/
 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);};};
const int MOD = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;


int main(void){

	string s;
	cin>>s;
	int p=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='p')p++;
	}
	cout<<floor((int)s.size()/2.0)-p<<endl;

}


Measured memory_bytes: 512
from collections import defaultdict


def factors(n):
    ps = []
    for i in range(2, int(n**0.5) + 1):
        while n % i == 0:
            n //= i
            ps.append(i)

    if n != 1:
        ps.append(n)

    return ps


d = defaultdict(lambda: 0)
n = int(input())
for i in range(2, n+1):
    fs = factors(i)
    for f in fs:
        d[f] += 1


c = 1
for _, v in d.items():
    c = c * (v + 1) % 1000000007

print(c)

Measured memory_bytes: 3316
//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define s(x) scanf("%d",&x)
#define rep(i,x) for(int i=0;i<x;i++)
int main()
{
	while(1)
	{
		string s; int n;
		cin >> n >> s;
		if(!n) return 0;
		for(int i=0;i<n;i++)
		{
			int cur=-1;
			int val=0;
			string nex="";
			s.pb('D');
			for(int j=0;j<s.size();j++)
			{
				if(cur==-1 || cur+'0'==s[j])
				{
					cur=s[j]-'0'; val++;
				}
				else
				{
					string f="";
					while(val){ f.pb(val%10+'0'); val/=10;}
					reverse(f.begin(),f.end());
					nex+=f; nex+=(cur+'0');
					cur=s[j]-'0'; val=1;
				}
			}
			s=nex;
		}
		cout << s << endl;
	}
}

Measured memory_bytes: 1344
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <functional>

using namespace std;

#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
template<class T> void pp(T a, T b){ for(T i = a; i != b; ++i) cout << *i << ' '; cout << endl; }

struct State {
  int x,y,d;
};

int W,H;
int mp[40][40][4];
const int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};

int bfs(void){
  int i;
  queue<State> q;
  State st; st.x = 0, st.y = 0, st.d = 1;

  q.push(st);
  while(!q.empty()){
    State now = q.front(); q.pop();
    if(now.y == H-1 && now.x == W-1) return now.d;
    //    cout << now.y << ' ' << now.x << endl;
    rep(i,4){
      if(mp[now.y][now.x][i] == 0){
        mp[now.y][now.x][i] = -1;
        int yy = now.y + dy[i];
        int xx = now.x + dx[i];
        State next; next.y = yy; next.x = xx; next.d = now.d + 1;
        q.push(next);
      }
    }
  }

  return 0;
}

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

  while(1){
    scanf("%d %d",&W,&H);
    if(W == 0 && H == 0) break;

    rep(i,40) rep(j,40) rep(k,4) mp[i][j][k] = -1;

    int d;
    rep(i,2*H-1){
      if(i%2 == 0){
        rep(j,W-1){
          scanf("%d",&d);
          if(d == 0){
            mp[i/2][j][2] = 0;
            mp[i/2][j+1][0] = 0;
          }
        }
      } else {
        rep(j,W){
          scanf("%d",&d);
          if(d == 0){
            mp[i/2][j][1] = 0;
            mp[(i/2) + 1][j][3] = 0;
          }
        }
      }
    }

    // mp[H][W][1] = 0;
    // rep(i,H) rep(j,W){ rep(k,4){ cout << mp[i][j][k] << endl; } cout << endl; }
    // cout << "check " << endl;
    
    cout << bfs() << endl;
  }

  return 0;
}

Measured memory_bytes: 964
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <iostream>
using namespace std;

bool judge(const int a[], int n, int m, int i, int sum);

int main(void)
{
	int n, a[20];
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];

	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int m;
		cin >> m;

		if (judge(a, n, m, 0, 0)) cout << "yes";
		else cout << "no";
		cout << endl;
	}

	return 0;
}

bool judge(const int a[], int n, int m, int i, int sum)
{
	if (i >= n) return false;
	int sum1 = sum;
	int sum2 = sum;

	if (judge(a, n, m, i + 1, sum1)) return true;

	sum2 += a[i];
	if (sum2 == m) return true;
	if (sum2 < m && judge(a, n, m, i + 1, sum2)) return true;
	return false;	
}

Measured memory_bytes: 3092
/*
AtCoder ABC150 C "Count Order".
next_permutation().
*/
#include<iostream>
#include<algorithm>
#include<vector>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
using namespace std;
typedef vector<int>   vi;

int n;

inline bool jud_same(vi a,vi b){
	REP(i,n){
		if(a[i]==b[i]){}
		else return false;
	}
	return true;
}

int main(){
	cin>>n;
	
	vi p(n),q(n);
	REP(i,n) cin>>p[i];
	REP(i,n) cin>>q[i];
	
	vi v=p;
	sort(ALL(v));
	
	int cnt=1;
	int pn,qn;
	do{
		if(jud_same(v,p)) pn=cnt;
		if(jud_same(v,q)) qn=cnt;
		cnt++;
	}while(next_permutation(ALL(v)));

	cout<<abs(pn-qn)<<endl;
}


Measured memory_bytes: 256