akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <tuple>
using namespace std;

#define ISEQ(c) (c).begin(), (c).end()
typedef long long ll;
typedef tuple<ll, int, ll> P;
const int MAX_V = 110000;
const ll INF = (ll)1e18+10;

struct edge {
  int to; ll cost;
};

vector<edge> G[MAX_V];
ll d[MAX_V], phs[MAX_V];
vector<ll> heights;

void dijkstra(int s, ll h) {
  priority_queue<P, vector<P>, greater<P> > que;
  fill(d, d+MAX_V, INF);
  fill(phs, phs+MAX_V, 0);
  d[s] = 0;
  phs[s] = h;
  que.push(P(0LL, s, h));
  while (!que.empty()) {
    P p = que.top(); que.pop();
    int v = get<1>(p);
    if (d[v] < get<0>(p)) continue;
    ll ph = get<2>(p);
    for (int i = 0, iL = G[v].size(); i < iL; i++) {
      edge e = G[v][i];
      ll extra, height;
      if (0 <= ph - e.cost and ph - e.cost <= heights[e.to]) {
	extra = 0LL;
	height = ph - e.cost;
      } else if (ph - e.cost < 0 and heights[v] >= e.cost) {
	extra = e.cost - ph;
	height = 0;
      } else if (heights[e.to] < ph - e.cost) {
	extra = ph - e.cost - heights[e.to];
	height = heights[e.to];
      } else {
	continue;
      }
      if (d[e.to] > d[v] + e.cost + extra) {
	d[e.to] = d[v] + e.cost + extra;
	phs[e.to] = height;
	que.push(P(d[e.to], e.to, height));
      }
    }
  }
}

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

  for (int i = 0; i < n; i++) {
    ll h;
    cin >> h;
    heights.push_back(h);
    G[i].clear();
  }

  for (int i = 0; i < m; i++) {
    int a, b;
    ll t;
    cin >> a >> b >> t;
    a--; b--;
    G[a].push_back(edge{b, t});
    G[b].push_back(edge{a, t});
  }

  dijkstra(0, x);
  if (d[n-1] >= INF)
    cout << -1 << endl;
  else
    cout << d[n-1]+heights[n-1]-phs[n-1] << endl;
}

Measured memory_bytes: 23944
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); (i)--)
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
using namespace std;
typedef long long lint;
typedef vector<vector<lint>> mat;

int main(){
    string k; int d; cin >> k >> d;
    int n = k.size();
    const lint mod = 1e9 + 7;
    lint dp[n+1][2][d];
    rep(i, n+1)rep(j, 2)rep(k, d) dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    rep(i, n)rep(j, 2)rep(l, d){
        int x = j ? 9 : k[i] - '0';
        rep(m, x+1){
            dp[i+1][j || m < x][(l+m) % d] += dp[i][j][l];
            dp[i+1][j || m < x][(l+m) % d] %= mod;
        }
    }
    cout << (dp[n][0][0] + dp[n][1][0] - 1 + mod) % mod << endl;
}

Measured memory_bytes: 16000
n = int(input())
l = [int(s)-1 for s in input()] 

if 1 in l:
    s = 0
    for i,a in enumerate(l):
        s += a*(n-1 == (i|(n-1-i)))
    print(s%2)
else:
    l = [i//2 for i in l]
    s = 0
    for i,a in enumerate(l):
        s += a*(n-1 == (i|(n-1-i)))
    print(s%2*2)

Measured memory_bytes: 20588
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<time.h>
#define forn(i,n) for(int i=0;i<n;i++)
#define clr(a,b) memset(a,b,sizeof(a))
#define ll long long
#define lowb(i) (i&(-i))
#define bug(n,m,x) forn(i,n){forn(j,m)printf("%d ",x[i][j]);puts("");}puts("")
using namespace std;
const int inf=1<<30;
const double eps=1e-6;
const double pi=acos(-1.0);
//const double inf = 1e10;

int n;
double v,X,Y;
double L[60],B[60],R[60],T[60];
double vx,vy;
const double g=9.8;
double gety(double x){
    double t=x/vx;
    return vy*t-g*t*t/2;
}
bool judge(){
    double bx=X,by=gety(X);
    if(by<Y)return false;
    forn(i,n){
        if(L[i]<X){
            double l=L[i],r=min(R[i],X);
            double y1=gety(l),y2=gety(r);
            if(y1>=B[i]&&y1<=T[i])return false;
            if(y2>=B[i]&&y2<=T[i])return false;
//            if(y1<)
        }
        if(L[i]<=bx&&R[i]>=bx){
            if(B[i]<=Y&&T[i]>=Y)return false;
            if(B[i]>=Y&&B[i]<=by)return false;
        }
    }return true;
}
int main(){
    //freopen("d:\\in.txt","r",stdin);
    scanf("%d%lf%lf%lf",&n,&v,&X,&Y);
    forn(i,n)scanf("%lf%lf%lf%lf",&L[i],&B[i],&R[i],&T[i]);
    double step=0.001;
    for(vx=step;vx<=v;vx+=step){
        vy=sqrt(v*v-vx*vx);
        if(judge()){
            puts("Yes");return 0;
        }
    }
    puts("No");
    return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    
    rep(i,n) cin >> a[i];
    sort(a.begin(),a.end());

    // for(auto e:a){
    //     cout <<e << " ";
    // }
    // cout << endl;
    int ans = 1e9;
    rep(i,n){
        //cout << a[i]-a[0] << " " << a[n-1]-a[i] << endl;
        int tmp = a[n-1]-a[0];
        tmp += min(a[i]-a[0],a[n-1]-a[i]);
        ans = min(ans,tmp);
//        ans = max(ans,(a[i]-a[0]) + (a[n-1] - a[i]) );
    }


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

Measured memory_bytes: 3600
#include<stdio.h>
int main(){
	int n,a,b,c,d,i,i2,p[100],m[100],t,l,r[100],aaa;
	scanf("%d",&n);
	for(i=0;i<=n;i++){
		p[i]=0;
		m[i]=0;
	}
	for(i=1;i<=n*(n-1)/2;i++){
		scanf("%d%d",&a,&b);
		m[a]++;
		m[b]++;
		scanf("%d%d",&c,&d);
		if(c>d){
			p[a]+=3;
		}
		else if(c<d){
			p[b]+=3;
		}
		else{
			p[a]++;
			p[b]++;
		}
	}
	for(i=1;i<=n;i++){
		m[i]=i;
	}
	for(i=1;i<=n;i++){
		for(i2=1;i2<=n;i2++){
			if(p[i]>p[i2]){
				t=p[i];
				p[i]=p[i2];
				p[i2]=t;
				t=m[i];
				m[i]=m[i2];
				m[i2]=t;
			}
		}
	}
	/*for(i=1;i<=n;i++){
		printf("%d %d\n",m[i],p[i]);
	}*/
	l=1;
	aaa=0;
	for(i=1;i<=n;i++){
		r[m[i]]=l;
		if(p[i]==p[i+1]){
			aaa++;
		}
		else{
			l=l+aaa+1;
			aaa=0;
		}
	}
	for(i=1;i<=n;i++){
		printf("%d\n",r[i]);
	}
}

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

#define pb push_back
#define MAX 100005
#define ff first
#define INF 1000000005
#define ss second
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}

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

int n,h[100005],k=2;
int dp[100005];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i = 0; i<n; ++i){
        cin>>h[i];
        dp[i] = INF;
    }
    dp[n-1]=0;
    for(int i = n-2;i>=0; i--){
        for(int j = 1; j<=k && i+j<n; ++j){
            dp[i] = min(dp[i],dp[i+j]+abs(h[i]-h[i+j])); 
        }
    }
    cout<<dp[0]<<"\n";
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(void)
{
	int i=0;
	int x, y;
	char pattern[8][8]={0};
	while(scanf("%8c%*c", pattern[i])!=EOF)
		if(++i>=8)break;

	printf("90\n");
	for(x=0; x<8; x++)
	{
		for(y=0; y<8; y++)
			printf("%c", pattern[7-y][x]);
		printf("\n");
	}

	printf("180\n");
	for(x=0; x<8; x++)
	{
		for(y=0; y<8; y++)
			printf("%c", pattern[7-x][7-y]);
		printf("\n");
	}

	printf("270\n");
	for(x=0; x<8; x++)
	{
		for(y=0; y<8; y++)
			printf("%c", pattern[y][7-x]);
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alp = "abcdefghijklmnopqrstuvwxyz";
void Yes() {cout << "Yes" << endl;}
void No() {cout << "No" << endl;}
void YES() {cout << "YES" << endl;}
void NO() {cout << "NO" << endl;}
void neg() {cout << -1 << endl;}

int main() {
  ll n;
  cin >> n;
  vector<ll> x(n), l(n);
  priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> range;
  for (ll i = 0; i < n; i++) {
    cin >> x.at(i) >> l.at(i);
    range.push({x.at(i) + l.at(i), x.at(i) - l.at(i)});
  }
  ll memo = range.top().at(0), cnt = 1;
  range.pop();
  for (int i = 1; i < n; i++) {
    if (range.top().at(1) >= memo) {
      cnt++;
      memo = range.top().at(0);
    }
    range.pop();
  }
  cout << cnt << endl;
}

Measured memory_bytes: 8372
while True:
    h, w = map(int, input().split())
    if h == w == 0:
        break
    else:
        s_dot = "#" + "." * (w - 2) + "#"
        s = "#" * w
        print(s)
        [print(s_dot) for _ in range(h - 2)]
        print(s)
        print("")


Measured memory_bytes: 5620
#include<stdio.h>

int main()

{

  int a,b,r;
  char op;
  while(scanf ("%d %c %d",&a,&op,&b)!=EOF){
  switch(op)
  {
    case '+': r=a+b;
    printf("%d\n",r);
    break;

    case '-': r=a-b;
    printf("%d",r);
    break;
   }
  }
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  ll n,h,w;
  cin>>n>>h>>w;
  cout << (n-h+1)*(n-w+1) << endl;
  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
s = input()

days = {
    'SUN': 7,
    'MON': 6,
    'TUE': 5,
    'WED': 4,
    'THU': 3,
    'FRI': 2,
    'SAT': 1
 }

print(days[s])


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N, L;
    cin >> N >> L;
    vector<string> S(N);
    for (auto& s : S) cin >> s;
    sort(S.begin(), S.end());
    for (const auto& s : S) cout << s;
    cout << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int k = sc.nextInt();
        
        // input:   3 5 4
        //          11100
        //          10001
        //          00111
        //
        // process: boardに切り込みを入れて
        //          どの部分も'1'がk個以下であるようにする
        //
        // output:  2 (縦1,横3の2箇所に切り込みを入れる)
        
        // board[i][j]: チョコレートの模様
        char[][] board = new char[h][w];
        for (int i = 0; i < h; i++) {
            String str = sc.next();
            for (int j = 0; j < w; j++) {
                board[i][j] = str.charAt(j);
            }
        }
        
        // bit: 横線の引き方のbit全探索
        // min: cutの最小値
        int min = (h-1)*(w-1);
        for (int bit = 0; bit < 1<<(h-1); bit++) {
            // bit -> group[i]: i行が属するグループ番号
            int[] group = new int[h];
            int g = 0;
            group[0] = g;
            for (int i = 0; i < h-1; i++) {
                // bitXが1なら次のグループにする
                if ((bit & (1<<i)) != 0) {
                    g++;
                }
                group[i+1] = g;
            }
            
            // cut: 横線の本数( + 縦線の本数)
            int cut = g;
            
            // count[i]: グループiの現在の'1'の個数
            // last: 最後に引いた縦線の位置
            // ok: 1列だけでk個を超すグループが存在しないならtrue
            int[] count = new int[g+1];
            int last = 0;
            boolean ok = true;
            
            // board -> cut
            // cut += 縦線の本数
            for (int i = 0; i < w; i++) {
                for (int j = 0; j < h; j++) {
                    if (board[j][i] == '1') {
                        count[group[j]]++;
                    }
                    
                    // '1'の個数がkを超えるグループがある場合、
                    // 今の列の前でカットし、その列は数え直し
                    if (count[group[j]] > k) {
                        if (last != i) {
                            cut++;
                            Arrays.fill(count, 0);
                            last = i;
                            i--;
                            break;
                        } else {
                            ok = false;
                        }
                    }
                }
            }
            
            if (ok) {
                min = Math.min(min, cut);
            }
        }
        System.out.println(min);
    }
}


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

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};


int main()
{
    int a,b;
    cin>>a>>b;
    char s[100][100];
    
    for(int i = 0; i < 50; i++)
    {
        for(int j = 0; j < 100; j++)
        {
            s[i][j]='#';
            s[i+50][j]='.';
        }
    }
    int acnt=1,bcnt=1;
    
    for(int i = 0; i < 50; i+=2)
    {
        for(int j = 0; j < 100; j+=2)
        {
            if(acnt<a)
            {
                s[i][j]='.';
                acnt++;
            }
        }        
    }
    
    for(int i = 51; i < 100; i+=2)
    {
        for(int j = 0; j < 100; j+=2)
        {
            if(bcnt<b)
            {
                s[i][j]='#';
                bcnt++;
            }
        }        
    }
    
    cout<<"100 100"<<endl;
    for(int i = 0; i < 100; i++)
    {
        
        for(int j = 0; j < 100; j++)
        {
            cout<<s[i][j];
        }
        cout<<endl;
    }
    

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

const ll mod=1e9+7;

//vector書き出し
template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}

typedef pair<int,int> P;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    vector<ll> a(n);
    ll x=0,y=0,z=0;//奇数, 素因数に2一つ, 4の倍数
    rep(i,n){
      cin>>a[i];
      if(a[i]%2==1){
        x++;
      }else if(a[i]%4==0){
        z++;
      }else{
        y++;
      }
    }
    ll cnt=z-n/2;
    if(cnt>=0){
      cout<<"Yes"<<endl;
    }else{
      if(y>=n-2*z){
        cout<<"Yes"<<endl;
      }else{
        cout<<"No"<<endl;
      }
    }
}

Measured memory_bytes: 1024
def bigger(a, b)
    if a > b then
        return a
    else
        return b
    end
end

def smaller(a, b)
    if a < b then
        return a
    else
        return b
    end
end

def sum(arr = [])
    s = 0
    for a in arr
        s += a
    end
    return s
end


input = STDIN.readlines.map{|line|line.strip.split()}
n = input[0][0].to_i
k = input[0][1].to_i
h_list = input.slice(1, n).map{|line|line[0].to_i}.sort
min = h_list[k - 1] - h_list[0]
(n - k).times do |i|
    min = smaller(min, h_list[i + k] - h_list[i + 1])
end
puts(min)

Measured memory_bytes: 18680
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector as V
import qualified Data.ByteString.Char8 as C
import Debug.Trace
import Data.List
import Control.Monad
import Data.Ord
import Data.Maybe


r :: Int -> IO (U.Vector Int)
r n = U.unfoldrN n (C.readInt . C.dropWhile (==' ')) <$> C.getLine

r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine


main :: IO ()
main = do
    [a,b,c] <- r'
    putStrLn $ if (4 * a * b) < (c - a - b)^2 && c-a-b > 0 then "Yes" else "No"



Measured memory_bytes: 380
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
#define dame { printf("No\n"); return 0;}
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e17)


signed main(){
    double n,k;
    cin >> n >> k;
    double res = 0.0;


    FOR(i,1,n+1){
        double tmp = 1.0;
        int hoge = i;
        while(hoge < k){
            hoge *= 2;
            tmp *= 2;
        }
        res += 1.0 / tmp;
    }
    cout << fixed << setprecision(13) << res / n << endl; 
}


Measured memory_bytes: 256
N=int(input())

ans = ""
def n(N):
    ans= ""
    for i in range(N):
        if N%26 ==0:
            ans = "z" +ans
            N -= 1
        else:
            ans = chr(64+ N%26) +ans
        
        if N <= 26:
            break
        N = N // 26
    return ans
    

print(n(N).lower())

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

int main() {
    int N;
    string S;
    cin >> N >> S;

    int count = 0;
    int i = 0;
    while(i < S.size()) {
        i = S.find("ABC", i);
        if (i == -1) break;
        else {
            count++;
            i += 3;
            if (i >= S.size()) break;
        }
    }

    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	double N = sc.nextDouble();
      	double X = sc.nextDouble();
      	int T = sc.nextInt();
      	int res = (int)(Math.ceil(N/X));
      	
      	System.out.println(res*T);
    }
}

Measured memory_bytes: 28820
/*  
    |\_/|
    |* *|
    \_+_/
*/
#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とか)と*/


  string s;
  
  cin>>s;
 
  for(int i=0;i<s.length();i++){
 
    if(s[i]==','){
      cout<<' ';
    }else{
      cout<<s[i];
    }
  }
 
  cout<<endl;

  return 0;

}




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

const double PI=acos(-1.0);

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

    if((a * b) % 2 == 0) {
        cout << "Even" << endl;
    } else {
        cout << "Odd" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

from collections import deque
def main():
    n, m = mi()
    cc = [0]*n
    for _ in range(m):
        a, b = mi()
        a -= 1
        b -= 1 
        cc[a] += 1
        cc[b] += 1
    for x in cc:
        if x%2 == 1:
            print('NO')
            return
    print('YES')



if __name__ == '__main__':
    main()

Measured memory_bytes: 10008
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(void){
    while (true){
        int h, w;
        cin >> h >> w;
        if (h == 0 || w == 0) break;
        for (int i = 0; i < h; i++){
            for (int j = 0; j < w; j++){
                if ((i + j) % 2 == 0) cout << "#";
                else cout << ".";
            }
            cout << endl;
        }
        cout << endl;
    }
}

Measured memory_bytes: 1152
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC159
{
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = Console.ReadLine();
            s = Console.ReadLine();
            var balls = s.Split().Select(int.Parse).ToArray();

            var p = new ProblemD();
            var ans = p.GetAnswer(balls);

            for (int i = 0; i < ans.Length; i++)
            {
                Console.WriteLine(ans[i]);
            }
        }
    }

    public class ProblemD
    {
        public long[] GetAnswer(int[] balls)
        {
            var ans = new long[balls.Length];

            var dic = new Dictionary<int, long>();
            for (int i = 0; i < balls.Length; i++)
            {
                if (dic.ContainsKey(balls[i]))
                {
                    dic[balls[i]]++;
                }
                else
                {
                    dic.Add(balls[i], 1);
                }
            }

            var total = 0L;
            foreach (var c in dic.Values)
            {
                if (c > 1)
                {
                    total += c * (c - 1) / 2;
                }
            }

            for (int i = 0; i < balls.Length; i++)
            {
                var n = dic[balls[i]];
                var c = 0L;
                if (n > 1)
                {
                    c = n * (n - 1) / 2 - (n - 1) * (n - 2) / 2;
                }
                ans[i] = total - c;
            }

            return ans;
        }
    }
}


Measured memory_bytes: 42572
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define Rep(i, s, n) for (int i = (int)s; i < (int)n; i++)
typedef long long ll;

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

    int a, b, c;
    cin >> a >> b >> c;

    int res = (c-a+b > 0) ? c-a+b : 0;
    cout << res << endl;
}

Measured memory_bytes: 3572
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#include <utility>
#define FOR(i, a, b) for (ll i = (a); i < (b); ++i)
#define REP(i, n) for (ll i = 0, i##_len = (n); i < i##_len; ++i)
#define INF 1e9
typedef long long int ll;
using namespace std;

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

    string ans = "CODEFESTIVAL2016";
    int cnt=0;
    REP(i,ans.size()){
        if(S[i]!=ans[i])    cnt++;
    }

    cout  << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
/*|In The Name Of Allah|*/

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3+5;
const int mod = 1e9+7;

int n;
int m;
char grid[N][N];
long long mem[N][N];

long long go(int i , int j){
    if(i == n && j == m)
        return 1;
    if(i > n || j > m)
        return 0;
    if(grid[i][j] == '#')
        return 0;
    if(~mem[i][j])
        return mem[i][j];
    return mem[i][j] = (go(i + 1 , j) + go(i , j + 1)) % mod;
}

int main(){
    scanf("%d%d" , &n , &m);
    for(int i = 1; i <= n; i++){
        getchar();
        for(int j = 1; j <= m; j++){
            grid[i][j] = getchar();
        }
    }
    memset(mem , -1 , sizeof mem);
    printf("%lld\n" , go(1 , 1));
}


Measured memory_bytes: 9216
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
constexpr int inf=1e9+7;
constexpr ll longinf=1LL<<60 ;
constexpr ll mod=1e9+7 ;

pair<double,double> solve(double x,double y,double z,double tx, double ty, double tz, double r, double tr){
    double a=tx*tx+ty*ty+tz*tz-tr*tr;
    double b=2*(x*tx+y*ty+z*tz+r*tr);
    double c=x*x+y*y+z*z-r*r;
    if(abs(a)<1e-9){
        if(abs(b)<1e-9)return {-1,-1};
        else return {-1,-c/b};
    }
    double d = b*b-4*a*c;
    if(d<0)return {-1,-1};
    if(b>0){
        return {(-b-sqrt(d))/(2*a), (-2*c)/(b+sqrt(d))};
    }
    else {
        return {(-b+sqrt(d))/(2*a), (-2*c)/(b-sqrt(d))};
    }
} 

void solve(int n){
    vector<double> x(n),y(n),z(n),vx(n),vy(n),vz(n),r(n),vr(n);
    rep(i,n)cin>>x[i]>>y[i]>>z[i]>>vx[i]>>vy[i]>>vz[i]>>r[i]>>vr[i];
    vector<pair<double,pair<int,int>>> die;
    rep(i,n){
        die.push_back({r[i]/vr[i],{i,i}});
    }
    rep(i,n)rep(j,i){
        auto res = solve(x[i]-x[j],y[i]-y[j],z[i]-z[j],vx[i]-vx[j],vy[i]-vy[j],vz[i]-vz[j],r[i]+r[j],vr[i]+vr[j]);
        if(res.first>=0){
            die.push_back({res.first,{i,j}});
        }
        if(res.second>=0){
            die.push_back({res.second,{i,j}});
        }
    }
    sort(die.begin(),die.end());
    vector<int> used(n);
    vector<double> ans(n);
    for(auto p:die){
        if(used[p.second.first]||used[p.second.second])continue;
        ans[p.second.first]=p.first;
        ans[p.second.second]=p.first;
        used[p.second.first]=1;
        used[p.second.second]=1;
    }
    rep(i,n)cout<<ans[i]<<endl;
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(12);
    int n;
    while(cin>>n,n!=0)solve(n);
    return 0;
}


Measured memory_bytes: 3840
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
//#define local
int main()
{
#ifdef local
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
#endif
    char s[100010];
    cin>>s;
    int k=strlen(s);
    if(s[0]==s[k-1]&&k%2||s[0]!=s[k-1]&&k%2==0) cout<<"Second";
    else cout<<"First";
    return 0;
}


Measured memory_bytes: 384
/*input
2 2
0 1
1 0
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}

//}}}
const ll maxn=305;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=998244353LL;
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}

bitset<maxn> b[maxn];

bitset<maxn> head[maxn];
bool vis[maxn];
int main()
{
	IOS;
	int n,m;
	cin>>n>>m;
	REP(i,n) REP(j,m){
		bool tmp;
		cin>>tmp;
		b[i][j]=tmp;
	}

	int cnt=0;
	REP(i,n){
		bool flag=0;
		for(int j=m-1;j>=0;j--) if(b[i][j]){
			if(vis[j]){
				b[i]^=head[j];
			}
			else{
				vis[j]=1;
				head[j]=b[i];
				flag=1;
				break;
			}
		}
		if(!flag) cnt++;
	}

	cout<<(mypow(2,n)-mypow(2,cnt)+MOD)*(mypow(2,m-1))%MOD<<'\n';

	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long m=1000000007;
        int N=sc.nextInt();
        int A=sc.nextInt();
        int B=sc.nextInt();
        long all= (npmodm_solve(2,N,m) - 1L + m) % m;        //2^N mod 10^9+7
        all -= Combi(N,A);
        all -= Combi(N,B);
        all += 2L * m;
        all%=m;
        pl(all);


    }
    public static void pl(Object o){
        System.out.println(o);
    }
    public static void p(Object o){
        System.out.println(o);
    }
    public static long Combi(int n,int r) {		// nCr
        long mod =1000000007L;
        if(r==0 || r==n) return 1L;

        if(r>n-r) {
            r=n-r;
        }

        int[] bunsi=new int[r];
        int[] bunbo=new int[r];

        for(int k=0; k<r; k++) {
            bunsi[k]=n-r+k+1;
            bunbo[k]=k+1;
        }

        for(int p=2; p<=r; p++) {
            int pivot=bunbo[p-1];
            if(pivot>1) {
                int offset=(n-r)%p;
                for(int k=p-1; k<r; k+=p) {
                    bunsi[k-offset]/=pivot;
                    bunbo[k]/=pivot;
                }
            }
        }

        long kotae=1;

        for(int k=0; k<r; k++) {
            if(bunsi[k]>1) {
                kotae*=bunsi[k];
                kotae%=mod;
            }
        }

        return kotae;
    }
    public static long npmodm_solve(long n,long p,long m) {		//n^p mod m

        long[] amari=new long[64];

        amari[0]=n%m;
        for(int i=0; i<62; i++) {
            amari[i+1]=amari[i]*amari[i]%m;
        }
        long tmp=p;
        int counter=0;
        long ans=1;
        while(tmp>0) {
            if(tmp%2==1) {
                ans=ans*amari[counter]%m;
                tmp/=2;
                counter++;
            }
            else {
                tmp/=2;
                counter++;
            }
        }
        return ans;
    }
}


Measured memory_bytes: 24532
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

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

int main(void){
  int N,W;
  while(cin>>N>>W){
    if(N==0) break;
    int go[1001];
    REP(i,N){
      cin>>go[i];
    }
    int now = 0;
    REP(i,W){
      int mas;
      cin>>mas;
      now+=mas;
      if(now>=N-1){
        cout<<i+1<<endl;
        REP(j,W-i-1)cin>>mas;
        break;
      }
      now+=go[now];
      if(now>=N-1){
        cout<<i+1<<endl;
        REP(j,W-i-1)cin>>mas;
        break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main() {
  int A , B , C , D;
  cin >> A >> B >> C >> D;
  if ((A + B) > (C + D)) {
    cout << "Left" << endl;
  }
  else if ((A + B) == (C + D)) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <utility>
#include <complex>
#include <functional>

/*
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
*/

using namespace std;

void trace(int a[], int n)
{
    printf("%d", a[0]);
    for (int i = 1; i < n; i++)
    {
        printf(" %d", a[i]);
    }
    printf("\n");
}

void insertionSort(int a[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int tmp = a[i]; //挿入する値
        int j;
        for (j=i-1; j >= 0 && a[j] > tmp; j--)
            a[j + 1] = a[j]; //要素を右にずらす
        a[j+1] = tmp;
        trace(a, n);
    }
}

int main()
{
    int n;
    scanf("%d", &n);

    int a[105];
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    trace(a, n);
    insertionSort(a, n);
}


Measured memory_bytes: 3164
//Author : pakhandi
//
using namespace std;

#include <bits/stdc++.h>

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int

#define IGNORE cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');

const ll INF = (1LL << 58);

#ifdef BUGGY
	bool DEBUG = 1;
#endif
#ifndef BUGGY
	bool DEBUG = 0;
#endif

int N;
ll a[101];

int main()
{
	a[0] = 2;
	a[1] = 1;

	for(int i = 2; i < 87; i++) {
		a[i] = a[i - 1] + a[i - 2];
	}

	cin >> N;
	cout << a[N];

	return 0;
}
/*
	Powered by Buggy Plugin
*/

Measured memory_bytes: 256
def is_ok(ev,val,v,srchd,ok)
	srchd[v] = true
	flga = false
	flgb = false
	ev.each{|v_of_ev|
		if(ok[v_of_ev])
			case val[v_of_ev]
			when "A"
				flga = true
			when "B"
				flgb = true
			end
		end
		if(flga && flgb)
			break
		end
	}
	if(!flga || !flgb)
		# break this vertex
		ok[v] = false
		return false
	end
	return true
end
def search(e,val)
	stack = [] # stack
	srchd = Array.new(e.size){false} # is searched flag
	ok = Array.new(e.size){true}
	# init
	e.each_with_index{|ev,v|
		if(!srchd[v] && !is_ok(ev,val,v,srchd,ok))
			chain(e,val,v,srchd,ok)
		end
	} 
	# detect cyclic
	# passed = Array.new(e.size){false} # is searched flag
	# for i in 0..(N-1)
	# 	if(!passed[i])
	# 		stack = [] # stack
	# 		e[i].each{|v|
	# 			stack.push([v,s]) #v,d to v
	# 		} 
	# 		while(!stack.empty?)
	# 			curv,curp = stack.pop
	# 			if(passed[curv])
	# 				# return true
	# 			end
	# 			passed[curv]=true
	# 			e[curv].each{|vv|
	# 				stack.push([vv,v])
	# 			}
	# 		end
	# 	end
	# end
	for i in 0..(N-1)
		return true if ok[i]
	end
	return false
end

def chain(e,val, s,srchd,ok)
	stack = [] # stack
	# init
	e[s].each{|v|
		stack.push([v,s]) #v,d to v
	} 
	while(!stack.empty?)
		curv,curp = stack.pop
		srchd[curv]=true
		if(!is_ok(e[curv],val,curv,srchd,ok))
			e[curv].each{|vv|
				if(vv != curp && ok[vv])
					stack.push([vv,curv])
				end
			} 
		end
	end
end


N,M=gets.chomp.split(' ').map{|n| n.to_i}
Val=gets.chomp.split('')
E = Array.new(N){[]}
1.upto(M){
	p=gets.chomp.split(' ').map{|n| n.to_i}
	p[0]-=1
	p[1]-=1
	E[p[0]].push(p[1])
	E[p[1]].push(p[0])
}
if(search(E,Val))
	puts "Yes"
else
	puts "No"
end


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

using namespace std;

typedef long long ll;
const int N = 2e5 + 10;
ll m, n;

ll sum[N];
ll a[N];
ll k;

map<ll, ll> ma;
// (sum[r] - sum[l -1]) % k == r - l + 1;

int main()
{
	scanf("%lld%lld", &n, &k);
	for (int i = 1; i <= n; i ++)
	{
		scanf("%lld", &a[i]);
		sum[i] = (sum[i - 1] % k + a[i] % k) % k;
	}
	for (int i = 1; i <= n; i ++)
	{
		sum[i] = ((sum[i] - i % k) % k + k) % k;
	}
	ll ans = 0;
	ma[sum[0]] ++;
	for (int i = 1; i <= n; i ++)
	{
		if(i >= k) ma[sum[i - k]]--;
		ans += ma[sum[i]];
		ma[sum[i]] ++;
	}
	cout <<ans << endl;
}


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

int main() {
    int x;
    long long s;
    cin >> x;
    if(x>=0 && x<=4) {
        cout << 0;
        return 0;
    }
    int c = x%500;
    s = (x/500)*1000;
    s += (c/5)*5;
    cout << s;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef _WIN32
#include "debug.hpp"
#endif
using namespace std;

#define rep(i,N) repf(i,0,N)
#define reps(i,N) repfs(i,1,N)
#define repf(i,a,b) for(int i=a;i<b;i++)
#define repfs(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,N) for(int i=N-1;i>=0;i--)
#define reprs(i,N) for(int i=N;i>0;i--)
#define pb push_back

template<typename T> 
void chmax(T &a,T b){ a = max(a, b);};
template<typename T> 
void chmin(T &a,T b){ a = min(a, b);};

typedef long long ll;
typedef pair<int,int> P;
const int INF = 100000000;
const int MOD = 1000000007;
const int dx[9] = { 0, 1,  0, -1, 1,  1, -1, -1, 0};
const int dy[9] = { 1, 0, -1,  0, 1, -1, -1,  1, 0};
//--------------------------------------//
int a,b,c;
ll k;

void solve(){
	if(k%2==0){
		cout<<a-b<<endl;
	}
	else
		cout<<b-a<<endl;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin>>a>>b>>c;
	cin>>k;
		solve();
	return 0;
}


Measured memory_bytes: 256
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)
	k := getNextInt(scanner)

	cutey := make([]int, 0)
	yosupot := make([]int, 0)

	for i := 1; i <= n/i; i++ {
		cutey = append(cutey, i)
		if i < n/i {
			yosupot = append(yosupot, n/i)
		}
	}
	for i := len(yosupot) - 1; i >= 0; i-- {
		cutey = append(cutey, yosupot[i])
	}
	for i := len(cutey) - 1; i > 0; i-- {
		cutey[i] -= cutey[i-1]
	}

	dp := makeInts(k+1, len(cutey)+1)
	for i := 1; i < len(cutey)+1; i++ {
		dp[0][i] = 1
	}

	mod := int64(1e9 + 7)
	for d := 1; d < k+1; d++ {
		for i := 1; i < len(cutey)+1; i++ {
			dp[d][i] = (dp[d][i-1] + dp[d-1][len(cutey)+1-i]*int64(cutey[i-1])) % mod
		}
	}

	fmt.Fprintln(writer, dp[k][len(cutey)])

	writer.Flush()
}

func makeInts(h, w int) [][]int64 {
	index := make([][]int64, h, h)
	data := make([]int64, h*w, h*w)
	for i := 0; i < h; i++ {
		index[i] = data[i*w : (i+1)*w]
	}
	return index
}


Measured memory_bytes: 56576
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#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,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

struct mint {
    ll x;
    mint(ll x=0):x(x%MOD){}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
};

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

    int n = l.length();

    vector<vector<mint>> dp(100005, vector<mint>(2, 0));
    dp[0][0] = 1;

    rep(i, n) {
        dp[i+1][1] += dp[i][1]*3;
        if (l[i] == '1') {
            dp[i+1][0] += dp[i][0]*2;
            dp[i+1][1] += dp[i][0];
        }
        else {
            dp[i+1][0] += dp[i][0];
        }
    }

    mint ans = dp[n][0] + dp[n][1];
    cout << ans.x << endl;
    return 0;
}

Measured memory_bytes: 5760
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<bitset>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(long long)((n)-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define inc(x,y) {x+=(y);if(x>=mod)x-=mod;}
#define dec(x,y) {x-=(y);if(x<0)x+=mod;}
#define spln(i,n) (i==n?'\n':' ')
using namespace std;
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar())&&c!='-')if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
bitset<50005> a[50005];
int t,n,m,i,j,px[100005],py[100005],vis[50005];
char ans[100005];
int main()
{
	scanf("%d%d%d",&n,&m,&t);
	fz1(i,m){
		scanf("%d%d",&px[i],&py[i]);
	}
	if(t==1){
		fz1(i,n) a[i][i]=1;
		fz1(i,m){
			a[px[i]]=a[py[i]]=(a[px[i]]|a[py[i]]);
		}
		fz1(i,n) if(a[i].count()==n) break;
		if(i>n){
			puts("-1");
			return 0;
		}
		vis[i]=1;
		fd1(i,m){
			if(vis[px[i]]){
				vis[py[i]]=1;
				ans[i]='^';
			}
			else if(vis[py[i]]){
				vis[px[i]]=1;
				ans[i]='v';
			}
			else ans[i]='v';
		}
		fz1(i,m)putchar(ans[i]);puts("");
	}
	else{
		if(n==2){
			puts("-1");
			return 0; 
		}
		vector<int> seq;
		fz1(i,m){
			if(px[i]<=3&&py[i]<=3){
				seq.push_back(i);
			}
			else{
				ans[i]='^';
			}
		}
		fz1(i,3) vis[i]=1;
		i=0;j=0;
		fz0k(i,seq.size()){
			int t=px[seq[i]]^py[seq[i]];
			if(!vis[t]){
				ans[seq[i-1]]='^'+'v'-ans[seq[i-1]];
				vis[t]=1;
			}
			ans[seq[i]]='^';
			vis[px[seq[i]]]=1;
			vis[py[seq[i]]]=0;
		}
		fz1(i,m){
			putchar(ans[i]);
		}
		puts("");
	}
	return 0;
}

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

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)

#define fi first
#define se second
#define pb push_back

const ll MOD = 1e9+7;

inline void in() {}
template<class T, class... Ts>
inline void in(T& x, Ts&... xs) {
	int c, s=0; x=0;
	while (c=getchar(), c!='-'&&(c<'0'||c>'9'));
	if (c=='-') s=1, c=getchar();
	do x=x*10+(c-'0'); while (c=getchar(), c>='0'&&c<='9');
	if (s) x=-x;
	in(xs...);
}
inline void ins(char *s) {
    char c; while(c=getchar(), c<33); do *s++=c; while(c=getchar(), c>32); *s=0;
}

int a[100000], b[100000], c[100000], d[100000];

int main() {
	int n;
	in(n);
	rep(i,0,n) in(a[i]);
	rep(i,0,n) in(b[i]);
	if (a[n-1]!=b[0]) cout<<"0\n", exit(0);
	if (n==1) cout<<"1\n", exit(0);
	rep(i,1,n-1) {
		if (a[i]==a[i-1]&&b[i]==b[i+1]) c[i]=min(a[i],b[i]);
		else c[i]=1;
		if (a[i]!=a[i-1]&&a[i]>b[i]) cout<<"0\n", exit(0);
		if (b[i]!=b[i+1]&&b[i]>a[i]) cout<<"0\n", exit(0);
		if (a[i]!=a[i-1]&&b[i]!=b[i+1]&&a[i]!=b[i]) cout<<"0\n", exit(0);
	}
	c[0]=c[n-1]=1;
	ll an = 1;
	rep(i,0,n) {
		an *= c[i];
		an %= 1000000007;
	}
	cout<<an<<endl;
}


Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0; i < (n); i++)
#define all(c) (c).begin(), (c).end()

struct Team {
  int i, u, a, p;
};

// team1 < team2 ならtrueを返す関数
bool comp(Team team1, Team team2) {
  if (team1.a != team2.a) return team1.a > team2.a;
  if (team1.p != team2.p) return team1.p < team2.p;
  return team1.i < team2.i;
}

// 選抜基準を満たしているならtrue
bool can_qualify(int num_u, int num_qualified) {
  if (num_qualified < 10) return num_u < 3;
  if (num_qualified < 20) return num_u < 2;
  if (num_qualified < 26) return num_u < 1;
  return false;
}

int main() {
  int n;
  while(cin >> n, n) {
    vector<Team> teams(n);
    rep(i, n) {
      cin >> teams[i].i >> teams[i].u >> teams[i].a >> teams[i].p;
    }
    sort(all(teams), comp);

    const int MAX_U = 1001;
    int num_qualified = 0; // 選抜された数
    vector<int> num_u_qualified(MAX_U, 0); // 所属毎の選抜された数
    rep(i, n) {
      if (can_qualify(num_u_qualified[teams[i].u], num_qualified)) {
        num_qualified++;
        num_u_qualified[teams[i].u]++;
        cout << teams[i].i << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int f(vector<int> ct){
    int sz = ct.size();
    int ret = 0;
    for(int i=sz; i>=3; --i){
        rep(j,sz-i+1){
            int num = 12345;
            for(int k=j; k<j+i; ++k) num = min(num, ct[k]);
            ret += 3*num;
            for(int k=j; k<j+i; ++k) ct[k] -= num;
        }
    }

    rep(i,sz) ret += ct[i];
    return ret;
}

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

    vector<int> a(26),d(10);
    for(char c:s){
        if(isdigit(c)) ++d[c-'0'];
        else ++a[c-'a'];
    }

    cout << f(a) + f(d) << endl;
    return 0;
}



Measured memory_bytes: 3228
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
int dp[1<<12];
int a[2000],n,m;
int c[20];
int merge(int val,int num){
	for(int i=1;i<=num;i++)val|=(1<<(c[i]-1));
	return val;
}
int main(){
	memset(dp,0x3f,sizeof(dp));
	cin>>n>>m;dp[0]=0;
	for(int i=1;i<=m;i++){
		int val,b;cin>>val>>b;
		for(int j=1;j<=b;j++)cin>>c[j];
		for(int j=0;j<(1<<12);j++){
			dp[merge(j,b)]=min(dp[merge(j,b)],dp[j]+val);
		}
	}
	if(dp[(1<<n)-1]>1e9)dp[(1<<n)-1]=-1;
	cout<<dp[(1<<n)-1];
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#define M 1000000007
#define pi 3.141592653589793
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int a[200000],i,max1=-1,max2=-1,flag=0,flagi;
    for(i=0;i<n;i++)
        {scanf("%d",&a[i]);
        if(a[i]>max1) {max1=a[i];flagi=i;}
        }
    for(i=0;i<n;i++)
    {if(a[i]==max1) flag++;
    if(flag>1) {max2=max1;break;}
    if(a[i]!=max1&&a[i]>max2)
        max2=a[i];
    }
    for(i=0;i<n;i++)
        if(i==flagi)
        printf("%d\n",max2);
        else
        printf("%d\n",max1);
    return 0;
}


Measured memory_bytes: 2304
#include <iostream>
using namespace std;
int main(){
	int takasa[10];

	for (int i = 0; i < 10; i++) {
		cin >> takasa[i];
	}

	//????????????
	for (int i = 0; i < 9; i++) {
		for (int j = i+1; j < 10; j++) {
			if (takasa[i] <takasa[j]) {
				swap (takasa[i],takasa[j]);
			}
		}
	}
	
	for (int i = 0; i < 3; i++) {
		cout << takasa[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
h, w, a, b = map(int, input().split())

ans = [['0' for _ in range(w)] for _ in range(h)]
for i in range(b):
    for j in range(a):
        ans[i][j] = '1'

for i in range(b, h):
    for j in range(a, w):
        ans[i][j] = '1'

for x in ans:
    print(''.join(x))


Measured memory_bytes: 12788