akhauriyash/Code-Regression huggingface dataset:
import sys
readline = sys.stdin.readline

W,H,N = map(int,readline().split())
minX = 0
minY = 0
maxX = W
maxY = H

for i in range(N):
  x,y,a = map(int,readline().split())
  if a == 1:
    minX = max(minX,x)
  elif a == 2:
    maxX = min(maxX,x)
  elif a == 3:
    minY = max(minY,y)
  elif a == 4:
    maxY = min(maxY,y)

print(max(0,maxX - minX) * max(0,maxY - minY))

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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

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

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

int main(){
    std::cout<<std::fixed<<std::setprecision(10);

    ll H;
    ll W;

    cin >> H >> W;
    vector<vector<char>> S(H+1, vector<char>(W+1, '.'));

    REP(i, H){
        REP(j,W){
            cin >> S[i][j];
        }
        S[i][W] = '#';
    }
    REP(j, W){
        S[H][j] = '#';
    }


    vector<vector<int>> HorizonTable(H+1, vector<int>(W+1, 0));
    vector<vector<int>> VerticalTable(H+1, vector<int>(W+1, 0));

    // Horizon
    for(int i = 0; i < S.size(); i++){
        int s = 0;
        int count = 0;
        for( int j = 0; j < S[i].size(); j++ ){
            if( S[i][j] == '#' ){
                HorizonTable[i][j] = 0;
                for( int k = s; k < j; k++){
                    HorizonTable[i][k] = j-s;
                    //cout << (j-s) << ",";
                }
                s = j+1;
                //cout << 0 << ",";
            }
        }
        //cout << endl;
    }

    // Vertical
    for(int j = 0; j < S[0].size(); j++){
        int s = 0;
        int count = 0;
        for( int i = 0; i < S.size(); i++ ){
            if( S[i][j] == '#' ){
                VerticalTable[i][j] = 0;
                for( int k = s; k < i; k++){
                    VerticalTable[k][j] = i-s;
                    //cout << (i-s) << ",";
                }
                s = i+1;
                //cout << 0 << ",";
            }
        }
        //cout << endl;
    }

    int ans = 0;
    for( int i = 0; i < H; i++){
        for( int j = 0; j < W; j++ ){
            ans = std::max(ans, VerticalTable[i][j]+HorizonTable[i][j]-1);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 35712
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;



int main(){
    ll n;
    cin>>n;
    vector<ll> a(n),b(n);
    for(auto &i:a){cin>>i;}
    for(int i=0;i<n;i++){b[i]=a[i];}
    sort(b.begin(),b.end());
    map<ll,bool> M;
    for(int i=0;i<n;i++){M[b[i]]=i&1;}
    ll count=0;
    for(int i=0;i<n;i+=2){if(M[a[i]]){count++;}}
    cout<<count<<endl;
    
    
    return 0;
}


Measured memory_bytes: 8064
// abc136c.cpp : Build Stairs
#include <bits/stdc++.h>
using namespace std;
#define in(x) cin>>(x)

int main(){
  int n; in(n);
  int a = -1;
  bool f = true;
  for(int i=0;i<n;i++){
    int h; in(h);
    if(a>h){ f = false; break; }
    else if(a<h) a = --h;
  }
  cout<< (f? "Yes":"No") <<endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define rep(i, n) for ( int i = 0; i < n; i++)
#define MAX 100
#define INFTY (1<<21)
int G[MAX][MAX], n;

void prim(){
    int D[MAX], V[MAX], P[MAX], sum = 0;
    rep(i, n) { D[i] = INFTY; V[i] = false; P[i] = -1; }
    D[0] = 0;

    while(1){
	int u, minv = INFTY;
	rep(i, n) if ( !V[i] && minv > D[i]) { 
	    minv = D[i], u = i; 
	}
	if ( minv == INFTY ) break;
	V[u] = true;
	sum += G[u][P[u]];
	rep(v, n){
	    if ( !V[v] && G[u][v] < D[v] ){
		D[v] = G[u][v];
		P[v] = u;
	    }
	}
    }

    cout << sum<< endl;
}

main(){
    int m, s, t, c;
    char ch;
    while( cin >> n >> m && n ){
	rep(i, n) rep(j, n) G[i][j] = INFTY;
	rep(i, m) {
	    cin >> s >> ch >> t >> ch >> c; 
	    G[s][t] = G[t][s] = c/100-1;
	}
	prim();
    }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int,int> P;
const int INF=(int)1e9;
const int MOD=(int)1e9+7;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
};

int main(){
  int N;
  cin>>N;
  int a[205];
  for(int t=0;t<N;t++){
    cin>>a[t];
  }


  int cont=0;
  while(true){
  bool flag=true;
  for(int t=0;t<N;t++){
    if(a[t]%2==1){
      flag=false;
    }
    a[t]/=2;
  }
  if(!flag)break;
  cont++;
}

cout<<cont<<endl;
 return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
template <class T>
bool find(vector<T> v, T key) {
	for (size_t i = 0; i < v.size(); i++)
		if (v[i] == key)return true;
	return false;
}
int main() {
	string s;
	getline(cin, s);
	vector<string>v;
	map<string, int>mp;
	int m = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == ' ') {
			string str = s.substr(m, i - m);
			if (find(v, str))mp[str]++;
			else { v.push_back(str); mp[str] = 1; }
			m = i + 1;
		}
	}
	string str = s.substr(m, s.size() - m);
	if (find(v, str))mp[str]++;
	else { v.push_back(str); mp[str] = 1; }
	string ans1, ans2;
	int splatoon = 0;
	for (int i = 0; i < v.size(); i++) {
		if (mp[v[i]] > splatoon) { ans1 = v[i]; splatoon = mp[v[i]]; }
		if (ans2.size() < v[i].size())ans2 = v[i];
	}
	cout << ans1 << ' ' << ans2 << '\n';
	char ch; cin >> ch;
}

Measured memory_bytes: 3020
#include <iostream>
#include <vector>
#include <algorithm>

int main(){
	int n,m;
	while(std::cin >> n >> m){
		if(n == 0 && m == 0){
			break;
		}
		std::vector<int> vegetable(n,0);
		for(int i = 0; i < n; ++i){
			std::cin >> vegetable[i];
		}
		std::sort(vegetable.begin(), vegetable.end(), std::greater<int>());
		int price = 0;
		for(int i = 0; i < n; ++i){
			price += vegetable.at(i);
		}
		for(int i = 1; i <= n/m; ++i){
			price -= vegetable.at(i * m - 1); 
		}
		std::cout << price << std::endl;
	}
	return 0;
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define m (l+r)/2
#define lson k<<1
#define rson k<<1|1
const int mod=998244353;
const int N=2e5+5;
ll tree[N<<2];
ll s[N];
int lzy[N<<2];
void pushdown(int k,int l,int r)
{
    if(lzy[k]==0)return ;
    lzy[lson]=lzy[rson]=lzy[k];
    tree[lson]=((s[m]-s[l-1]+mod)%mod)*lzy[k]%mod;
    tree[rson]=((s[r]-s[m]+mod)%mod)*lzy[k]%mod;
    lzy[k]=0;
    return ;
}
ll query(int k,int ql,int qr,int l,int r)
{
    if(ql<=l&&qr>=r)return tree[k];
    ll res=0;
    pushdown(k,l,r);
    if(ql<=m)
        res+=query(lson,ql,qr,l,m);
    if(qr>m)
        res+=query(rson,ql,qr,m+1,r);
    tree[k]=tree[lson]+tree[rson];
    return res;

}
void modify(int k,int ql,int qr,int l,int r,int val)
{
    if(ql<=l&&r<=qr)
    {
        lzy[k]=val;
        tree[k]=((s[r]-s[l-1]+mod)%mod)*val%mod;
        return ;
    }
    pushdown(k,l,r);
    if(ql<=m)
        modify(lson,ql,qr,l,m,val);
    if(qr>m)
        modify(rson,ql,qr,m+1,r,val);
    tree[k]=(tree[lson]+tree[rson])%mod;
    return ;
}
int main()
{
    int n,q;
    int x,y,z;
    scanf("%d%d",&n,&q);
    s[1]=1;
    for(int i=2;i<=n;i++)
    {
        s[i]=(s[i-1]*10+1)%mod;
    }
    modify(1,1,n,1,n,1);
    while(q--)
    {
        scanf("%d%d%d",&x,&y,&z);
        x=n-x+1;
        y=n-y+1;
        swap(x,y);
        modify(1,x,y,1,n,z);
        printf("%lld\n",tree[1]);
    }
}


Measured memory_bytes: 11548
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int n;
    cin >> n;
    int ans = -1e9,Min = INT_MAX;
    for(int i = 0;i < n;i++)
    {
        int r;
        cin >> r;
        if(i >= 1)
        {
            ans = max(ans,r - Min);
        }
        Min = min(Min,r);
    }
    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define REVETSE(c) reverse((c).begin(),(c).end())
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define ALL(a)  (a).begin(),(a).end()
// int gcd(int a,int b){return b?gcd(b,a%b):a;}
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> T maxt(T x,T y) {
    if (x>y) return x;
    else return y;
}
template<class T> T mint(T x,T y) {
    if (x>y) return y;
    else return x;
}
//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
//cout << fixed << setprecision(10) << ans << defaultfloat << endl;
typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<double> Vd;
typedef vector<string> Vs;

//小数出力
double print_double(double d){printf("%.8f", d);}

long long m = 1e9+7, mod = 1e9+7;
//逆元　a/b の modをとるとき -> a*modinv(b)%mod
long long modinv(long long a, long long m = 1e9+7) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

//約数列挙
vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}


int main() {
  string s,t;
  cin >> s >> t;
  int lens = s.length(),lent = t.length();
  vector<Vi> dp(lens+1, Vi(lent+1,0));
  rep(i,lens) {
    rep(j,lent){
      if (s[i]==t[j]){
        dp[i+1][j+1] = dp[i][j]+1;
      }
      else {
        dp[i+1][j+1] = maxt(dp[i+1][j],dp[i][j+1]);
      }
    }
  }
  string str = "";
  int i = lens,j = lent;
  while (i>=1 && j>=1){
    if (s[i-1]==t[j-1]){
      str.push_back(s[i-1]);
      i--;j--;
    }
    else if (dp[i-1][j]>dp[i][j-1]) i--;
    else j--;
  }
  reverse(ALL(str));
  cout << str << endl;
  
}

Measured memory_bytes: 35584
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

vector<Int> s;
int N;

int main(void) {
    cin>>N;

    for(int i = 0;i < N;i++) {
        Int t;
        cin>>t;
        s.push_back(t);
    }

    Int ans = 0;
    for(int c = 1;c < N;c++) {
        if((N-1) % c == 0) {
            Int score = 0;
            int left = 0;
            int right = N-1;
            for(;left < right; left += c,right -= c) {
                score += s[left]+s[right];

                ans = max(ans, score);
            }

        } else {
            Int score = 0;
            int left = 0;
            int right = N-1;
            for(; left < N-1 && right > c;left += c, right -= c) {
                score += s[left]+s[right];
                ans = max(ans, score);
            }
        }
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
	int x,y,a,b,c;
	cin >> x >> y >> a >> b >> c;
	vector<long long> ps,qs,rs;
	for(int i = 0; i < a; i++)
	{
		long long e;
		cin >> e;
		ps.push_back(e);
	}
	for(int i = 0; i< b; i++)
	{
		long long e;
		cin >> e;
		qs.push_back(e);
	}
	for(int i = 0; i< c; i++)
	{
		long long e;
		cin >> e;
		rs.push_back(e);
	}

	long long ans = 0;
	sort(ps.rbegin(),ps.rend());
	sort(qs.rbegin(),qs.rend());

	for(int i = 0;i < x;i++)
		rs.push_back(ps[i]);
	for(int i = 0;i < y;i++)
		rs.push_back(qs[i]);

	sort(rs.rbegin(),rs.rend());
	
	for(int i = 0; i < x+y; i++)
		ans += rs[i];

	cout << ans << endl;

}

Measured memory_bytes: 8048
import java.util.Scanner;
import java.lang.Math;

public class Main{
	public static void main(String[]args){
		Scanner sc = new Scanner(System.in);
		double x1 = sc.nextDouble();
		double y1 = sc.nextDouble();
		double x2 = sc.nextDouble();
		double y2 = sc.nextDouble();
		
		System.out.println(Math.sqrt(Math.pow(x1-x2,2)+Math.pow(y1-y2, 2)));
		
	}
}

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

// calc min(a*xs[i] + b)
template <class T>
struct LiChaoTree {
  struct Line {
    T a, b;
    Line(T a, T b) : a(a), b(b) {}
    inline T get(T x) const { return a * x + b; }
    inline bool over(const Line &b, const T &x) const {
      return get(x) < b.get(x);
    }
  };
  vector<T> xs;
  vector<Line> seg;
  int xsize;
  LiChaoTree() {}
  LiChaoTree(const vector<T> &x, T INF) : xs(x) {
    xsize = 1;
    while(xsize < xs.size()) xsize <<= 1;
    while(xs.size() < xsize) xs.push_back(xs.back() + 1);
    seg.assign((xsize << 1) - 1, Line(0, INF));
  }
  void update(Line &x, int k, int l, int r) {
    int mid = (l + r) >> 1;
    bool chl = x.over(seg[k], xs[l]),
         chr = x.over(seg[k], xs[mid]);
    if(chr) swap(seg[k], x);
    if(l + 1 >= r) return;
    if(chl != chr)
      update(x, 2 * k + 1, l, mid);
    else
      update(x, 2 * k + 2, mid, r);
  }
  void update(T a, T b) {
    Line nowl(a, b);
    update(nowl, 0, 0, xsize);
  }
  T query(int k) {
    const T x = xs[k];
    k += xsize - 1;
    T ans = seg[k].get(x);
    while(k > 0) {
      k = (k - 1) >> 1;
      ans = min(ans, seg[k].get(x));
    }
    return ans;
  }
};

long long n, c;
vector<long long> h;
LiChaoTree<long long> lct;

long long solve();

int main() {
  cin >> n >> c;
  h.resize(n);
  for(int i = 0; i < n; ++i) cin >> h[i];
  cout << solve() << endl;
  return 0;
}

long long solve() {
  lct = LiChaoTree<long long>(h, (long long)(1e16));
  lct.update(-2 * h[0], h[0] * h[0]);
  for(int i = 1; i < n; ++i) {
    long long now = lct.query(i) + h[i] * h[i] + c;
    lct.update(-2 * h[i], now + h[i] * h[i]);
    if(i == n - 1) return now;
  }
  assert(0);
  return -1;
}


Measured memory_bytes: 12924
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
	int h, w;
	cin >> h >> w;
	vector<vector<int>> a(h, vector<int>(w, 0));
	rep(i, h)rep(j, w) cin >> a[i][j];

	vector<vector<int>> ans;
	rep(i, h)rep(j, w - 1) {
		if (a[i][j] % 2 == 1) {
			a[i][j]--;
			a[i][j + 1]++;
			ans.push_back({ i,j,i,j + 1 });
		}
	}
	rep(k, h - 1) {
		if (a[k][w-1] % 2 == 1) {
			a[k][w-1]--;
			a[k + 1][w-1]++;
			ans.push_back({ k,w-1,k + 1,w-1 });
		}
	}
	cout << ans.size() << endl;
	rep(i, ans.size()) {
		cout << ans[i][0]+1 << " " << ans[i][1]+1 << " " << ans[i][2]+1 << " " << ans[i][3]+1 << endl;
	}
}

Measured memory_bytes: 10032
import java.util.Scanner;				
public class Main {				
				
   public static void main(String[] args){				
    int intput1;				
    Scanner in = new Scanner(System.in);				
		    intput1 = in.nextInt();		
	 if (1 <= intput1 && intput1 <= 100){			
     System.out.println(intput1*intput1*intput1);     				
    }				
 }				
}				
				


Measured memory_bytes: 26092
import heapq

k,t=map(int,input().split())
a=list(map(int,input().split()))
a=list(map(lambda x: -1*x,a))
heapq.heapify(a)

h=heapq.heappop(a)
h+=1
pre_h=h

while(len(a)>0):
    h=heapq.heappop(a)
    if(h==0):
        break
    else:
        h+=1
        heapq.heappush(a, pre_h)
        pre_h=h

print(-1*pre_h)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_N 100001
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define FOR(i, a, b) for(ll i=a; i<b; i++)
#define REP(i, n) for(ll i=0; i<n; i++)
#define REV(i, n) for(ll i=n-1; i>=0; i--)
#define ALL(v) v.begin(), v.end()
#define pb push_back
const ll INF = 9e18;
ll n, m, a[MAX_N];

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

ll lcm(ll a, ll b){
    return a * b / gcd(a, b);
}

signed main(){
    cin >> n >> m;
    REP(i, n){
        cin >> a[i];
        a[i] /= 2;
    }
    ll k = a[0];
    REP(i, n-1){
        k = lcm(k, a[i+1]);
    }
    REP(i, n){
        if((k / a[i]) % 2 == 0){
            cout << 0 << endl;
            return 0;
        }
    }
    cout << ((m / k) + 1) / 2 << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define FORR(I,A,B) for(ll I = ((B)-1); I >= (A); --I)
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
struct edge{ll from, to, cost;};


// http://sesenosannko.hatenablog.com/entry/2017/09/01/214852
struct Bellman_Ford{
	struct edge{ll from, to, cost;};
	ll inf = 1e16;
	vector<edge> es;
	vector<ll> d;
	ll V,E;
	void init(ll v,ll e){
		V = v; E = e;
		d.resize(V);
	}
	void shortest_path(ll s){
		FOR(i,0,V) d[i] = inf;
		d[s] = 0;
		FOR(i,0,V){
			FOR(j,0,E){
				edge e = es[j];
				if(d[e.from]!=inf && d[e.to]>d[e.from] + e.cost){
					d[e.to] = d[e.from] + e.cost;
				}
			}
		}
	}
	bool find_negative_loop(){// all graph
		FOR(i,0,V)d[i] = 0;
		FOR(i,0,V){
			FOR(j,0,E){
				edge e = es[j];
				if(d[e.to]>d[e.from] + e.cost){
					d[e.to] = d[e.from] + e.cost;
					if(i == V-1) return true;
				}
			}
		}
		return false;
	}
	bool find_negative_loop(ll s){// from s
		ll cnt = 0;
		FOR(i,0,V)d[i]=inf;
		d[s]=0;
		while(true){
			bool update = false;
			cnt++;
			FOR(i,0,E){
				edge e = es[i];
				if(d[e.from] != inf && d[e.to]>d[e.from] + e.cost){
					d[e.to] = d[e.from] + e.cost;
					if(cnt == V){
						return true;
					}
					update = true;
				}
			}
			if(! update)break;
		}
		return false;
	}
	bool shortest_path(int s, int t){ // t: destination
		FOR(i,0,V)d[i] = inf;
		d[s] = 0;
		FOR(i,0,2*V){
			FOR(j,0,E){
				edge e = es[j];
				if(d[e.from]!=inf && d[e.to]>d[e.from] + e.cost){
					d[e.to] = d[e.from] + e.cost;
					if(i>=V-1 && e.to==t) return true;
				}
			}
		}	
		return false;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	Bellman_Ford bf;
	ll V,E,r;
	cin >> V >> E >> r;
	bf.init(V,E);
	FOR(i,0,E){
		ll a,b,c;
		cin >> a >> b >> c;
		bf.es.push_back({a,b,c});
	}
	if(bf.find_negative_loop(r)){
		cout << "NEGATIVE CYCLE" << endl;
	}else{
		FOR(i,0,V){
			if(bf.d[i]==bf.inf)cout << "INF" << endl;
			else cout << bf.d[i] << endl;
		}
	}
}


Measured memory_bytes: 3296
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<iostream>

using namespace std;

int main()
{
	int a,b;
	long long sum;
	while(~scanf("%d %d",&a,&b))
	{
		sum=a*b;
		if(sum%2==1)
			printf("Odd\n");
		if(sum%2==0)
			printf("Even\n");
	}
	return 0;
}


Measured memory_bytes: 256
# Dinic's algorithm
from collections import deque


class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow


h, w = map(int, input().split())
dinic = Dinic((h+1)*(w+1))
maze = [list(input()) for _ in range(h)]
start = 0
goal = 0
INF = 10 ** 9 + 7

for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            continue
        if maze[i][j] == 'S':
            start = (i + 1) * (w + 1) + j + 1
            dinic.add_edge(start, j + 1, INF)
            dinic.add_edge(start, (i+1)*(w+1), INF)
        elif maze[i][j] == 'T':
            goal = (i + 1) * (w + 1) + j + 1
            dinic.add_edge(j + 1, goal, INF)
            dinic.add_edge((i+1)*(w+1), goal, INF)
        dinic.add_multi_edge(j + 1, (i + 1) * (w + 1) + j + 1, 1, 1)
        dinic.add_multi_edge((i+1)*(w+1), (i+1)*(w+1) + j+1, 1, 1)
ans = dinic.flow(start, goal)
print(ans if ans < 10**9 else -1)


Measured memory_bytes: 11184
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main()
{
	int n,k,Max=0,Gcd=0;
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		Max=max(Max,x);
		Gcd=gcd(Gcd,x);
	}
	puts(k%Gcd==0&&k<=Max?"POSSIBLE":"IMPOSSIBLE");
	return 0;
}

Measured memory_bytes: 256
N, P = [int(x) for x in input().split()]


def make_prime(n):
    array = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt = cnt + 1
                temp = temp // i
            array[i] = cnt

    if temp != 1:
        array[temp] = 1

    if array == {}:
        array[n] = 1

    return array


primes = make_prime(P)

result = 1
for key, value in primes.items():
    if value >= N:
        result *= key ** (value // N)

print(result)


Measured memory_bytes: 9396
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int mod = 1e+9 + 7;
const int INF = 1e+9;

ll S[200005];

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

    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        S[i+1] = S[i] + a;
        S[i] = (S[i] - i) % k;
        while(S[i] < 0){
            S[i] += k;
        }
    }
    S[n] = (S[n] - n) % k;
    while(S[n] < 0){
        S[n] += k;
    }
    map<int, int> mp;
    ll res = 0;
    for(int i = 0; i <= n; ++i){
        res += mp[S[i]];
        ++mp[S[i]];
        if(i >= k-1)  --mp[S[i - (k-1)]];
    }

    cout << res << endl;
}

Measured memory_bytes: 11264
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

template<typename t1, class t2>
void input(t1 count,t2 array) {
	for(t1 i = 0;i < count;i++) {
		cin >> array[i];
	}
}

template<typename t1, class t2>
void output(t1 count,t2 array) {
	for(t1 i = 0;i < count;i++) {
		cout << array[i];
		if(i != count - 1) cout << " ";
	}
	cout << endl;
}

ll gcd(ll a,ll b) {
	int x = min(a,b),y = max(a,b);
	if(x == 0) return y;
	else return gcd(x,y % x);
}

int main(void) {
	ll a,b;
	cin >> a >> b;
	cout << gcd(a,b) << endl;
}



Measured memory_bytes: 3096
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

const int MOD = 1000000007, INF = 1111111111;
using namespace std;
using lint = long long;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (int i = 0; i < (int)vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	}
	return os;
}

#ifdef _DEBUG
template <class Head>
void dump(const char* str, Head &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + 1, t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	string S;
	cin >> S;

	int left = 0, right = 0;

	for (int i = 0; i < N; i++) {

		if (S[i] == '(') left++;
		else {
			if (left) left--;
			else right++;
		}

	}

	cout << string(right, '(') + S + string(left, ')') << "\n";

	return 0;
}

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

#define ONLINE_JUDGE
#define pb(a) push_back(a)
#define ALL(a) a.begin(), a.end()
#define FOR(x,to) for(x=0;x<(to);x++)

using ll = long long;

const int E5 = 1e5;

//////////// Solution /////////////////////////////////

void solve() {
	int A,B,K;
	cin >> A >> B >> K;
	if (B-A+1 <= 2*K) {
		for (int i = A; i <= B; ++i) {
			cout << i << '\n';
		}
	} else {
		for (int i = A; i <= A+K-1; ++i) {
			cout << i << '\n';
		}
		for (int i = B-K+1; i <= B; ++i) {
			cout << i << '\n';
		} 
	}	

}	

/////////// End Solution ///////////////////////////////////////

//////// Initialization ////////////////////////////////////

int main() {

	#ifndef ONLINE_JUDGE
	FILE *FIN = freopen("/home/danil/prog/input.txt", "r", stdin);
	clock_t time_start = clock();
	#endif

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	solve();

	#ifndef ONLINE_JUDGE
	fclose(FIN);
	cerr << "\x1b[031m\n-----------------\nTime=" << (ll)((double)(clock()-time_start) / CLOCKS_PER_SEC * 1000) << "ms\n\x1b[0m";
	#endif

	return 0;
}

//////// End Initialization ///////////////////////////////////////


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
 int a,b,c,d;
  cin>>a>>b>>c>>d;
  int flag=1;
  while(a>0&&c>0){
    if(flag%2!=0)
      c=c-b;
    else
      a=a-d;
    flag++;
  }
  if(a>0)
    cout<<"Yes\n";
    else
      cout<<"No\n";
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
int vis[MAXN][3];
struct node
{
	int u,dis;
	int r;
	node(int u=0,int dis=0,int r=0):u(u),dis(dis),r(r) {}
};
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int S,T,n,m;
queue<node> q;
int bfs()
{
	vis[S][0]=1;
	q.push(node(S,0,0));
	while(!q.empty())
	{
		node k=q.front();
		q.pop();
		int u=k.u;
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			int rr=(k.r+1)%3;
			if(v==T && rr==0)
				return (k.dis+1)/3;	
			if(vis[v][rr])
				continue;
			vis[v][rr]=1;
			q.push(node(v,k.dis+1,rr));
		}
	}
	return -1;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
	}
	S=read(),T=read();
	cout<<bfs()<<endl;
	return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
//macros
using namespace std;
typedef long long ll;
typedef pair<int, int > P;
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
const long long int mod = 1e9 + 7;
int H;
int W;
int cnt;
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
char s[50][50];
int d[50][50];
int bfs(){
    queue<P> q;
    rep(i,0,W){
        rep(j,0,H){
            d[i][j] = -1;
        }
    }
    q.push(P(0,0));
    d[0][0] = 0;

    while(!q.empty()){
        P p = q.front(); q.pop();
        if(p.first == W-1 && p.second == H-1) break;
        rep(i,0,4){
            int nx = p.first + dx[i], ny = p.second + dy[i];
            if(0<=nx && nx<W && 0<=ny && ny<H
            && s[ny][nx] != '#' && d[nx][ny] == -1){
                q.push(P(nx,ny));
                d[nx][ny] = d[p.first][p.second] + 1;
                //cout << nx << "," << ny << " " <<d[nx][ny] << endl;
            }                       
        }

    }
    return d[W-1][H-1];
}



int main()
{
    cin >> H >>W;
    rep(i,0,H){
        rep(j,0,W){
            cin >> s[i][j];
            if(s[i][j]=='.') cnt++;
        }
    }
    int res = bfs();
    if(res == -1){
        cout << "-1" << endl;
        return 0;
    }else{
        res = cnt-res-1;
        cout << res << endl;
    }
    return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define L "\n"
#define S " "
#define ll long long
#define pb push_back
#define mp make_pair
#define vi std::vector<int>
#define si std::set<int>
#define vl std::vector<long long>
#define qi std::queue<int>
#define de(a) cout << #a << "  ------>  " << a << "\n"
#define SIZE 100002
#define INF INT_MAX
#define FOR(i, n) for (i = 1; i <= n; i++)
#define FASTIO                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)

using namespace std;
int dp[SIZE][3], N, h[SIZE][3];
bool flag[SIZE][3];

int hap(int i, int act)
{
    int a1, a2;
    if (i == N)
    {
        flag[i][act] = 1;
        return dp[i][act] = h[i][act];
    }
    if (flag[i + 1][(act + 1) % 3])
        a1 = dp[i + 1][(act + 1) % 3];
    else
        a1 = hap(i + 1, (act + 1) % 3);
    if (flag[i + 1][(act + 2) % 3])
        a2 = dp[i + 1][(act + 2) % 3];
    else
        a2 = hap(i + 1, (act + 2) % 3);
    flag[i][act] = 1;
    return dp[i][act] = h[i][act] + max(a1, a2);
}

void solve()
{
    int i;
    cin >> N;
    FOR(i, N)
    {
        cin >> h[i][0];
        cin >> h[i][1];
        cin >> h[i][2];
    }
    int res = max(hap(1, 0), max(hap(1, 1), hap(1, 2)));
    cout << res << L;
}
int main()
{
    FASTIO;
    // #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    // #endif
    int t;
    // cin >> t;
    // while (t--)
    solve();
    return 0;
}

Measured memory_bytes: 7552
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;


int main(){

	stack<int> bsli;
	stack<pair<int, int> > provs;
	char t;
	int area=0;

	for( int i=0; cin>>t; i++ ){

		if( t=='\\' ){
			bsli.push(i);

		}else if( t=='/' && bsli.size() >0 ){
			int tp=bsli.top();bsli.pop();

			area += i -tp;
			int a= i -tp;

			


			while( provs.size() && provs.top().first >tp ){
				a+= provs.top().second; provs.pop();

			}
			provs.push(make_pair(tp, a)); //????????????\???????????¨??????????????§????????????????±?
			
		}
	}

	vector<int> ans;
	int temp=0;
	while( provs.size() ){
		ans.push_back(provs.top().second); provs.pop();
	}

	reverse(ans.begin(), ans.end());
	cout<<area<<endl;
	cout<<ans.size()<<flush;
	for( unsigned int i=0; i<ans.size(); i++ ){
		cout<<' '<<flush;
		temp +=ans[i];
		cout<<ans[i];
	}
	cout<<endl;
}

		

Measured memory_bytes: 1288
#include <bits/stdc++.h>
#include <ext/hash_map>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

#define REP(i,n) for( (i)=0 ; (i)<(n) ; (i)++ )
#define rep(i,x,n) for( (i)=(x) ; (i)<(n) ; (i)++ )
#define REV(i,n) for( (i)=(n) ; (i)>=0 ; (i)-- )
#define FORIT(it,x) for( (it)=(x).begin() ; (it)!=(x).end() ; (it)++ )
#define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define rforeach(it,c) for(__typeof((c).rbegin()) it=(c).rbegin();it!=(c).rend();++it)
#define foreach2d(i, j, v) foreach(i,v) foreach(j,*i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define SZ(x) ((int)(x).size())
#define MMS(x,n) memset(x,n,sizeof(x))
#define mms(x,n,s) memset(x,n,sizeof(x)*s)
#define pb push_back
#define mp make_pair
#define NX next_permutation
#define UN(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define CV(x,n) count(all(x),(n))
#define FIND(x,n) find(all(x),(n))-(x).begin()
#define ACC(x) accumulate(all(x),0)
#define PPC(x) __builtin_popcountll(x)
#define LZ(x) __builtin_clz(x)
#define TZ(x) __builtin_ctz(x)
#define mxe(x) *max_element(all(x))
#define mne(x) *min_element(all(x))
#define low(x,i) lower_bound(all(x),i)
#define upp(x,i) upper_bound(all(x),i)
#define NXPOW2(x) (1ll << ((int)log2(x)+1))
#define PR(x) cout << #x << " = " << (x) << endl ;

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

const int OO = (int) 2e9;
const double eps = 1e-9;

int n, x;
hash_map<int, int> cnt;
int mx1 = -1, mx2 = -1;
ll res;

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
//	freopen("in.txt", "rt", stdin);
//	freopen("out.txt", "wt", stdout);
#endif
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		cnt[x]++;
	}
	for (auto it : cnt) {
		if (it.second > 1) {
			if (it.first > mx1) {
				mx2 = mx1;
				mx1 = it.first;
			} else if (it.first > mx2) {
				mx2 = it.first;
			}
		}
		if (it.second > 3) {
			res = max(res, it.first * 1LL * it.first);
		}
	}
	if (mx2 != -1)
		res = max(res, mx1 * 1LL * mx2);
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 5688
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const ll MOD = 1e9 + 7;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }

vector<int> ans;
bool calc(vector<int> b) {
   int m = b.size();
   for (int i = m - 1; i >= 0; i--) {
      // cout << i << " " << b[i] << endl;
      if (i + 1 == b[i]) {
         vector<int> c(m);
         copy(b.begin(), b.end(), c.begin());
         b.erase(b.begin() + i);
         if ((int)b.size() == 0) {
            ans.push_back(i + 1);
            return true;
         }
         if (calc(b)) {
            ans.push_back(i + 1);
            return true;
         }
         else break;
      }
   }
   return false;
}

int main() {
   int N;
   cin >> N;
   vector<int> b;
   int tmp;
   for (int i = 0; i < N; i++) {
      cin >> tmp;
      b.push_back(tmp);
   }
   if (!calc(b)) cout << "-1" << endl;
   else {
      for (int i = 0; i < N; i++) {
         cout << ans[i] << endl;
      }
   }
   return 0;
}


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


int main() {

  int n;
  cin>>n;

  vector<int> A(n);
  map<int, int> dup;
  for(int i=0;i<n;i++){
    cin>>A.at(i);
    if(dup.count(A.at(i)))
      dup.at(A.at(i))++;
    else
      dup[A.at(i)]=1;
  }

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

  int A_max=A.at(n-1);
  vector<bool> check(A_max+1,false);
  for(int i=0;i<n;i++){
    if(check.at(A.at(i))==false){
      for(int j=2*A.at(i);j<=A_max;j+=A.at(i)){
          check.at(j)=true;
      }
    }
  }

  int cnt=0;
  for(int i=0;i<n;i++){
    if(check.at(A.at(i))==false&&dup.at(A.at(i))<=1)
      cnt++;
  }

  cout<<cnt<<endl;

    return 0;
}


Measured memory_bytes: 13384
#include <cstdio>

int main() {
  int N, M;
  scanf("%d%d", &N, &M);
  static int t[100005];
  for (int i = 1, a, b; i <= M; ++i)
    scanf("%d%d", &a, &b), t[a] ^= 1, t[b] ^= 1;
  for (int i = 1; i <= M; ++i) 
    if (t[i]) {
      puts("NO");
      return 0;
    }
  puts("YES");
  return 0;
}


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

const int mxN = 1e5;
int h[mxN],dp[mxN+1],n,k;

int main(){
    cin >> n >> k; 
    for(int i=0 ; i< n ; ++i) cin >> h[i];
    memset(dp,0x3f,sizeof((dp)));
    dp[0]=0;
    dp[1] = abs(h[1]-h[0]);
    /*
    for(int i=1 ; i<n ;++i){
        dp[i] = min(dp[i],
    }
    for(int i=0 ; i< n ; ++i)cout << dp[i] <<" ";
    cout <<"\n";*/
    for(int i=2 ; i<n ;++i){
        for(int j = 1 ; j<=min(k,i) ; ++j)
            dp[i] = min(dp[i],dp[i-j]+ abs(h[i]-h[i-j]));
    }
    /*for(int i=0 ; i< n ; ++i)cout << dp[i] <<" ";
    cout <<"\n";*/
    cout << dp[n-1];
}

Measured memory_bytes: 4360
N, K = map(int, input().split())
*p, = map(int, input().split())
Ep = [(x + 1) / 2 for x in p]
S = [0 for _ in range(N+1)]

for i in range(N):
  S[i+1] = S[i] + Ep[i]
m = 0
for i in range(N):
  if i + K > N:
    break
  m = max(m, S[i+K]-S[i])
print(m)

Measured memory_bytes: 86536
#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }


int main() {
    string L;
    cin >> L;
    int N = L.size();
    v2ll dp1(N + 1, vll(3, 0));
    v2ll dp2(N + 1, vll(3, 0));
    //dp1[N] = 1;
    //dp2[N] = 1;
    dp1[N][0] = 1;
    dp2[N][0] = 1;
    ll p = 1000000007;
    for (int i = N - 1; i >= 0; i--) {
        rep(j, 3) {
            rep(k, 3) {
                dp1[i][j] = (dp1[i][j] + dp1[i + 1][k]) % p;
                       
            }
        }

        if(L[i] == '1') {
            rep(j, 3) {
                rep(k, 3) {
                    if(j == 0)
                        dp2[i][j] = (dp2[i][j] + dp1[i + 1][k]) % p;
                    else
                        dp2[i][j] = (dp2[i][j] + dp2[i + 1][k]) % p;

                }
            }
        }
        else {
            rep(j, 3) {
                rep(k, 3) {
                    if (j == 0)
                        dp2[i][j] = (dp2[i][j] + dp2[i + 1][k]) % p;
                    
                }
            }
        }
       
    }

    cout << (dp2[0][0] + dp2[0][1] + dp2[0][2])% p << endl;
    return 0;
}

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

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef long double ld;

const int MAXN = 11;
const int MAXQ = 51;

ld get_shit(ld val) {
	ld res = val - (ll) (val);
	return res;
}

void solve() {
	ll a, b, n;
	cin >> a >> b >> n;
	ld minshit = min(b - 1, n);
	minshit /= (ld) (b);
	ld minus = minshit * (ld) (a);
	//cout << minshit << ' ' << minus << endl;
	ld ans = (ld) (a) * minshit - get_shit(minus);
	//cout << ans << endl;
	cout << (ll) (ans) << "\n";
} 

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0; 
}

Measured memory_bytes: 3640
object Main extends App {

  import scala.io.StdIn._

  solve
  def solve: Unit = {
    val Array(n, m) = readLine.trim.split(' ')
    if (n == "0") return
    val value = m.toBasedInt(n.toInt)
    println(List(31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2).filter(n.toInt % _ == 0).map{prime ⇒ countFactorInFactorial(value, prime) / countPrimeFactor(n.toInt, prime)}.min)
    solve
  }
  implicit class ToBase(val str: String) extends AnyVal {
    def toBasedInt(base: Int): Long = {
      str.foldLeft(0L){
          case (a, b) if b.isDigit ⇒ a * base + b.asDigit
          case (a, b) ⇒ a * base + b - 'A' + 10
        }
      }
  }
  def countPrimeFactor(value: Int, prime: Int): Int = {
    value % prime match {
      case 0 ⇒ 1 + countPrimeFactor(value / prime, prime)
      case _ ⇒ 0
    }
  }
  def countFactorInFactorial(value: Long, prime: Long): Long = {
    value match {
      case 0 ⇒ 0
      case _ ⇒ value / prime + countFactorInFactorial(value / prime, prime)
    }
  }
  implicit class Extension[T](val value :T) extends AnyVal {
    @inline
    def let[A](@inline func: T ⇒ A): A = func(value)
    @inline
    def also(@inline func: T ⇒ Unit): T = {func(value); value}
    @inline
    def takeIf(@inline predicate: T ⇒ Boolean): Option[T] = Some(value).filter(predicate)
  }
}


Measured memory_bytes: 79608
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <cctype>
#define ll long long
#define PI 3.14159265358979323846
using namespace std;

int main() {
	int n,m;
	cin>>n>>m;
	int a,b;
	int road[51][51]= {0};
	for(int i=0; i<m; i++) {
		cin>>a>>b;
		road[a][b]++;
		road[b][a]++;
	}
	for(int i=1; i<=n; i++) {
		int num=0;
		for(int j=1; j<=n; j++) {
			if(road[i][j]>0) {
				num+=road[i][j];
			}
		}
		cout<<num<<endl;
	}
	return 0;
}


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

int main(){
    long long a,b,f,g,l,x,k;
    cin>>a;
    cin>>b;
    f=b;
    g=b;
    l=b;
 
    for (k=0;k<=a-2;k++){
        cin>>x;
        if(x>f){
            f=x;
        }else if(x<g){
            g=x;
        }
    
        l=l+x;
    }
    cout<<g<<" "<<f<<" "<<l<<endl;
    

}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long x,a,b,c,ans=0;
    cin>>a>>b>>c>>x;
    for(int i=0;i<=a;i++)
        for(int j=0;j<=b;j++)
            for(int z=0;z<=c;z++){
                int k=i*500+j*100+z*50;
                if(k==x)
                   ans++;
                   if(k>x)
                   break;
            }
    cout<<ans<<endl;//输出ans的值(AT题都要打换行)
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
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; }
const int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(n*a, b) << endl;
}

Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N;

int main(){
	cin>>N;
	if(N==25){
		cout<<"Christmas"<<endl;
	}else if(N==24){
		cout<<"Christmas Eve"<<endl;
	}else if(N==23){
		cout<<"Christmas Eve Eve"<<endl;
	}else{
		cout<<"Christmas Eve Eve Eve"<<endl;
	}
}

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

int main() {
  int x;

  cin >> x;

  if (x > 3000) {
    cout << 1;
    return 0;
  }

  for (int i = 0; i < 30; i++)
    for (int j = 0; j < 30; j++)
      for (int k = 0; k < 30; k++)
        for (int l = 0; l < 30; l++)
          for (int n = 0; n < 30; n++)
            for (int m = 0; m < 30; m++)
              if (x ==
                  i * 100 + j * 101 + k * 102 + l * 103 + n * 104 + m * 105) {
                cout << 1;
                return 0;
              }

  cout << 0;

  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#define INF 1000000000000
using namespace std;
typedef long long ll;

struct edge{int to; ll cap; int rev;};

vector<edge> g[310];
bool used[310];

void add_edge(int from, int to, ll cap){
    g[from].push_back((edge){to,cap,(int)g[to].size()});
    g[to].push_back((edge){from,0,(int)g[from].size()-1});
}

ll dfs(int v,int t,ll f){
    if(v==t){
        return f;
    }
    used[v]=true;
    for(int i=0;i<g[v].size();i++){
        edge &e=g[v][i];
        if(!used[e.to]&&e.cap>0){
            ll d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                g[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

ll max_flow(int s,int t){
    ll flow=0;
    for(;;){
        memset(used,0,sizeof(used));
        int f=dfs(s,t,INF);
        if(f==0) return flow;
        flow+=f;
    }
}

int main(){
    int n;
    ll a,ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lld",&a);
        if(a<=0){
            add_edge(0,i+1,-a);
        }
        else{
            add_edge(i+1,n+1,a);
            ans+=a;
        }
        for(int j=2*(i+1);j<=n;j+=i+1){
            add_edge(i+1,j,INF);
        }
    }
    printf("%lld\n",ans-max_flow(0,n+1));
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define sd(x) scanf("%d",&(x))
#define pd(x) printf("%d",(x))
#define slld(x) scanf("%lld",&(x))
#define plld(x) printf("%lld",(x))
#define br printf("\n")
#define pi pair<int,int>
#define pii pair<long long int, long long int>
#define vi vector<int>
#define pb push_back
#define RESET(val) memset(val, 0, sizeof(val))
#define mp(a,b) make_pair(a, b)
#define fi first
#define se second
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define mod 1000000007
#define inf 10000000000000000
int power(int a,int b,int n){int ans=1;while(b>0){if(b%2==1)ans=(ans*a)%n;a=(a*a)%n;b/=2;}return ans;}

signed main(){
 //   freopen("input.txt","r",stdin);
   	int n;	cin>>n;
   	int cx = 0, cy = 0, ct = 0;
   	while(n--){
   		int t,x,y;
   		cin>>t>>x>>y; t = t-ct;
   		int tt = abs(x-cx) + abs(y-cy);
   		if(t >= tt && (t+tt)%2 == 0){
   			cx = x; cy = y; ct += t;
   		}
   		else{
   			cout<<"No";
   			return 0;
   		}
   	}
   	cout<<"Yes";
    return 0;
} 

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
int n;
char ch[200005];
int sm[200005];
void init(){
	std::cin>>(ch+1);
	n=std::strlen(ch+1);
	for(int i=1;i<=n;++i){
		ch[i]=(ch[i]=='B'?1:0);
	}
	sm[n+1]=0;
	for(int i=n;i>=1;--i){
		sm[i]=sm[i+1]+(ch[i]^1);
	}
	long long ans=0;
	for(int i=1;i<=n;++i){
		if(ch[i]){
			ans+=sm[i+1];
		}
	}
	printf("%lld",ans);
}

int main(){
	init();
	return 0;
}

Measured memory_bytes: 1280