akhauriyash/Code-Regression huggingface dataset:
// #pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define String std::string
#define fi first
#define se second
#define mp std::make_pair
#define Pair std::pair<ll, int>
#define Map std::map< int, int >
#define Vector std::vector<int>
 
using std::cin;
using std::cout;
using std::endl;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int N = 100000 + 5;
const int M = 1000 + 5;
const int K = 1e7 + 5;
const int MOD = 1e9 + 7;
const int inv2 = 500000004;
const int LOG = 40;
const ull BASE = 19260817;
const int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };
const int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };
// const double PI = acos(-1);
const double PI = 3.14159;

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
 
template<class T>
inline T readT() {
    T res = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + ch - '0';
    return res * f;
}
#define read readT<int>

namespace Comb{
const int N = 10 + 5;
inline void exgcd(ll a, ll b, ll &g, ll &x, ll &y) {
    if (!b) g = a, x = 1, y = 0;
    else exgcd(b, a % b, g, y, x), y -= x * (a / b);
}
 
inline ll inv(ll a) {
    ll g, res, tmp;
    exgcd(a, MOD, g, res, tmp);
    return ((res % MOD) + MOD) % MOD;
}
 
ll f[N], invFact[N];
 
inline void prepare() {
    f[0] = 1;
    int n = 200000;
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD;
    invFact[n] = inv(f[n]);
    for (int i = n - 1; i >= 1; i--) invFact[i] = invFact[i + 1] * (i + 1) % MOD;
}
 
inline ll C(int n, int m) {
    if (!m) return 1;
    if (n == m) return 1;
    if (m > n) return 0;
    if (m < 0) return 0;
    return f[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}
}

int main() {
    ll n, x;
    cin >> n >> x;
    cout << 3ll * (n - std::__gcd(n, x)) << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

class ABPare {

	long A;
	long B;

	public ABPare(long a, long b) {
		A = a;
		B = b;
	}

	public long getA() {
		return A;
	}

	public long getB() {
		return B;
	}
}

class BComp implements Comparator<ABPare> {
	public int compare(ABPare o1, ABPare o2) {
		if (o1.B == o2.B)
			return 0;
		return o1.B < o2.B ? -1 : 1;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		ArrayList<ABPare> ABList = new ArrayList<ABPare>(N);
		for (int i = 0; i < N; i++) {
			long A_i = sc.nextLong();
			long B_i = sc.nextLong();
			ABList.add(new ABPare(A_i, B_i));
		}
		sc.close();
		// これA，BのペアをB_i基準で昇順に並べ替えたらOKでは？

		Collections.sort(ABList, new BComp());

		// for (int i = 0; i < ABList.size(); i++) {
		// String str = "A_" + i + ":" + ABList.get(i).getA();
		// str += ",B_" + i + ":" + ABList.get(i).getB();
		// System.out.println(str);
		// }

		long sum_A = 0;
		for (int i = 0; i < ABList.size(); i++) {
			sum_A += ABList.get(i).getA();
			if (sum_A > ABList.get(i).getB()) {
				System.out.println("No");
				return;
			}
		}

		System.out.println("Yes");
	}
}

Measured memory_bytes: 108348
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<long long> a(n+1);
    for(int i=0; i<n+1; i++){
        cin >> a[i];
    }
    vector<long long> b(n);
    for(int i=0; i<n; i++){
        cin >> b[i];
    }
    long long ans=0;
    long long tmp1, tmp2;
    for(int i=0; i<n; i++){
        tmp1 = min(a[i],b[i]);
        b[i] = b[i] - tmp1;
        tmp2 = min(a[i+1],b[i]);
        a[i+1] = a[i+1] - tmp2;
        ans = ans + tmp1 + tmp2;
    }
    cout << ans << endl;
}



Measured memory_bytes: 4788
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
int mod=1e9+7;

signed main(){
  int n,a,b;
  cin>>n>>a>>b;
  cout<<min(a,b)<<" "<<max(0LL,a+b-n)<<endl;
}


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

int main(){
		int n;
		int j[1010], p[1010], q[1010], r[1010];
		int P, Q, R, C;

		while(cin >> n, n){
				bool isExist = false;
				for(int i=0; i < n; i++){
						cin >> j[i] >> p[i] >> q[i] >> r[i];
				}
				cin >> P >> Q >> R >> C;

				for(int i=0; i < n; i++){
						if(p[i]<=P && q[i]<=Q && r[i]<=R && (p[i]+r[i])*4+q[i]*9 <= C){
								cout << j[i] << endl;
								isExist = true;
						}
				}
				if(!isExist){
						cout << "NA" << endl;
				}
		}
}

Measured memory_bytes: 1176
import sys
input = sys.stdin.readline

mod = 10**9+7

N = int(input())
A = list(map(int, input().split()))

i = 0
c = 0
ans = 1
while i < N:
    if 2*c + 1 <= A[i]:
        i += 1
        c += 1
    else:
        ans = ans * (c+1) % mod
        i += 1
for n in range(1, c+1):
    ans = ans * n % mod
print(ans)

Measured memory_bytes: 14008
# ABC077 C
import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
C.sort()

result = 0
for i in range(N):
    target = B[i]
    a_num = bisect.bisect_left(A, target)
    b_num = len(C)-bisect.bisect_right(C, target)
    result += a_num*b_num
print(result)

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

using namespace std;
typedef pair<int,int> P;

int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

int h,w;
    char c[1000][1001];
    int ans[1000][1001];
    int memo=0;
    char spc;

int main(){
    queue<P> que;

    scanf("%d %d",&h,&w);
    scanf("%c",&spc);

    for(int i=0; i<h; i++){
        for(int j=0; j<=w; j++){
            scanf("%c", &c[i][j]);
            
            
            ans[i][j] = -1;
            if(c[i][j] == '#'){
                que.push(P(i,j));
            }
        }

    }
    
    while(que.size()){
        P xy = que.front(); que.pop();
        if(c[xy.first][xy.second]=='#'){ans[xy.first][xy.second]=0;}
        for(int i=0; i<4; i++){
            int nx=xy.first+dx[i], ny=xy.second+dy[i];
            
            if(0<=nx && nx<h && 0<=ny && ny<w && ans[nx][ny]==-1 && c[nx][ny]=='.'){
                que.push(P(nx,ny));
                ans[nx][ny] = ans[xy.first][xy.second] + 1;
                memo = max(ans[nx][ny],memo);
            }
        }
    }

    printf("%d\n",memo);
    return 0;
}

Measured memory_bytes: 13328
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define     bit_1(a)       __builtin_popcount(a)
#define     ull            unsigned long long
#define     ll             long long
#define     u              unsigned
#define     pb             push_back
#define     pf             push_front
#define     mpr            make_pair
#define     ins            insert
#define     ff             first
#define     ss             second
#define     vi             vector<int>
#define     vl             vector<ll>
#define     vstr           vector<string>
#define     si             set<int>
#define     sl             set<ll>
#define     li             list<int>
#define     pii            pair<int,int>
#define     pll            pair<ll,ll>
#define     mii            map<int,int>
#define     mll            map<ll,ll>
#define     ma             INT_MAX
#define     mi             INT_MIN
#define     mod            1000000007
#define     pi             3.14159265359
#define     e              2.71828182846
#define     inf            1000000000000000LL
#define     all(x)         x.begin(), x.end()
#define     lb(a,b,c)      lower_bound(a,a+b,c)-a
#define     ub(a,b,c)      upper_bound(a,a+b,c)-a
#define     lbv(a,c)       lower_bound(all(a),c)-a.begin()
#define     ubv(a,c)       upper_bound(all(a),c)-a.begin()
#define     srt1(a,b)      sort(a,a+b)
#define     srt2(a,b)      sort(a,a+b,greater<int>())
#define     gcd(a,b)       __gcd(a,b)
#define     lcm(a,b)       (a*(b/gcd(a,b)))
#define     harmonic(n)    0.57721566490153286l+log(n)
#define     mem(a, b)      memset(a, b, sizeof(a))
#define     orderset1      tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define     orderset2      tree<int,null_type,greater<int>,rb_tree_tag,tree_order_statistics_node_update>

///s.lower_bound(a),s.upper_bound(a), for set
///nCr(x, y) = nCr(x-1, y-1) + nCr(x-1, y)
///factorial digit   ((n * log10(n / e) +log10(2 * pi * n) /2.0));
/// lcm(a,b)=a/gcd(a,b)*b (handle overflow)

bool sortinrev1(const pair<int,int>&a,const pair<int,int>&b)
{
    //return (a.first > b.first);
    if(a.first==b.first)return (a.second>b.second);
    else return (a.first > b.first);
}
bool sortinrev2(const pair<int,int>&a,const pair<int,int>&b)
{
    //return (a.first > b.first);
    if(a.first==b.first)return (a.second<b.second);
    else return (a.first > b.first);
}
int fx[]={1,-1,0,0};
int fy[]={0,0,1,-1};


int main()
{
    /*int n;
    cin>>n;
    if(n>=30)cout<<"Yes\n";
    else cout<<"No\n";*/
    /*mll mp;
    ll n,d,xi,yi,ans=0;
    cin>>n>>d;
    while(n--){
        cin>>xi>>yi;
        ll p=ceil(sqrt((xi*xi)+(yi*yi)));
        if(p<=d)ans++;
    }
    cout<<ans<<endl;*/
    int n,ans=0;
    string str;
    cin>>n>>str;
    int w=count(str.begin(),str.end(),'W');
    int r=count(str.begin(),str.end(),'R');
    if(w==0){
        cout<<0<<endl;
        return 0;
    }
    for(int i=0;i<r;i++){
        if(str[i]=='W')ans++;
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 3760
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

/* include file*/
#include <functional>
#include <vector>
using namespace std;

template <class Monoid>
struct Segment {
  using Func = function<Monoid(Monoid, Monoid)>;

  vector<Monoid> node;
  Monoid ide;
  int n = 1;

  Func bin_f;
  Func update_f;

  Segment(const vector<Monoid>& init, Monoid ide_, Func f_, Func u_f)
    : bin_f(f_), ide(ide_), update_f(u_f) {
      int sz = init.size();
      while (n < sz) n *= 2;
      node.assign(n * 2 - 1, ide);
      for (int i = 0; i < sz; i++) node[i + n - 1] = init[i];
      for (int i = n - 2; i >= 0; i--)
        node[i] = bin_f(node[i * 2 + 1], node[i * 2 + 2]);
    }

  void update(int i, Monoid x) {
    i += n - 1;
    node[i] = update_f(node[i], x);
    while (i) {
      i = (i - 1) / 2;
      node[i] = bin_f(node[i * 2 + 1], node[i * 2 + 2]);
    }
  }

  Monoid get_inter(int a, int b, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    if (a <= l && r <= b) return node[k];
    if (r <= a || b <= l) return ide;

    Monoid lm = get_inter(a, b, k * 2 + 1, l, (l + r) / 2);
    Monoid rm = get_inter(a, b, k * 2 + 2, (l + r) / 2, r);
    return bin_f(lm, rm);
  }
};

// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2730414#1
// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2730425#1

int N;
i64 K;
vector<i64> a;

int main(){
  cin >> N >> K;
  a.resize(N);
  rep(i,0,N - 1) cin >> a[i];
  rep(i,0,N - 1) a[i] -= K;
  rep(i,1,N - 1) a[i] += a[i - 1];
  vector<i64> vec;
  rep(i,0,N - 1) vec.push_back(a[i]);
  sort(vec.begin(),vec.end());

  Segment<i64> seg(vector<i64>(N,1),0,[](i64 a,i64 b){return a + b;},[](i64 node,i64 x){return node + x;});

  i64 now = 0;
  i64 res = 0;

  rep(i,0,N - 1){
    int index = lower_bound(vec.begin(),vec.end(),now) - vec.begin();
    res += seg.get_inter(index,N);
    now = a[i];
    seg.update(lower_bound(vec.begin(),vec.end(),now) - vec.begin(),-1);
  }

  cout << res << endl;
}


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

using namespace std;

int main ()
{
  int answer = 0;
  int N = 0;
  cin >> N;
  
  vector<int> H(N);
  for (int i = 0; i < N; i ++)
  {
    cin >> H[i];
  }
  
  int tmp_h = 0;
  for (int i = 0; i < N; i ++)
  {
  	if (i == 0)
    {
      ++ answer;
      tmp_h = H[i];
    }
    else
    {
      if (H[i-1] <= H[i] && tmp_h <= H[i])
      {
        ++ answer;
        tmp_h = H[i];
      }
    }
  }
  
  cout << answer << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define lli long long int
#define vi vector<int>
#define vlli vector<lli>
#define vvi vector<vi >
#define str string
#define vs vector<str>
#define vb vector<bool>
#define slli set<lli>
#define mii map<int, int>
#define mlli map<int, lli>
#define msi map<str, int>
#define mp make_pair
#define pii pair<int, int>
#define pll pair<lli, lli>
#define vpii vector<pii >
#define vpll vector<pll >
#define pb push_back
#define loop(i, s, l, j) for(int i = s; i < l; i += j)
#define rloop(i, s, l, j) for(int i = s; i >= l; i -= j)
#define rep(i, n) loop(i,0,n,1)
#define rrep(i, n) rloop(i,n-1,0,1) 
#define fastio() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ft first
#define sd second   
#define mit mii::iterator
#define vit vi::iterator
#define all(a) a.begin(),a.end()
#define min3(a, b, c) min(a, min(b, c))
#define mod 1000000007
#define inf 1000000000
#define limit 200001
/**********************************************************************************************************************************************/
int dx4[4] = {0, -1, 0, 1};
int dy4[4] = {1, 0, -1, 0};
int dx8[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int Power(int base,int exp){int ans=1;  while(exp > 0){if(exp&1)ans=(1LL*ans*base)%mod; exp=exp>>1; base=(1LL*base*base)%mod;}  return ans;}
/**********************************************************************************************************************************************/ 

void input()
{
    int n,m,k;
    cin >> n >> m >> k;
    vlli a(n), b(m);
    rep(i,n)
    {
        cin >> a[i];
        if(i)
            a[i] += a[i-1];
    }
    rep(i,m)
    {
        cin >> b[i];
        if(i)
            b[i] += b[i-1];
    }

    int ans = 0;
    rep(i,n+1)
    {
        lli t = k - (i ? a[i-1] : 0);
        if(t < 0)
            continue;
        int j = (upper_bound(all(b), t) - b.begin());
        ans = max(ans, i + j);
    }
    cout << ans << '\n';


}
 
int main()
{
    

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
 
    fastio();
    int q = 1;
    //cin >> q;
    while(q--)
        input();
}

Measured memory_bytes: 6308
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sq = 1;
        while(sq*sq <= n){
            sq++;
        }
        sq--;
        System.out.println(sq*sq);
        sc.close();
    }

}


Measured memory_bytes: 23124
a, b = map(int, input().split(" "))

if (a < 0 and b < 0):
    if (a - b) % 2 == 0:
        print("Negative")
    else:
        print("Positive")
elif (a < 0 and b > 0):
    print("Zero")
else:
    print("Positive")

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

int n,m,dfn[10005],low[10005],dfncnt,ans=-1;
vector<int> g[10005];

void dfs(int x,int p){
    dfn[x]=low[x]=++dfncnt;
    for(int &y:g[x])if(!dfn[y]){
        dfs(y,x);
        low[x]=min(low[x],low[y]);
    }else if(y!=p){
        low[x]=min(low[x],dfn[y]);
    }
    ans+=dfn[x]==low[x];
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    dfs(1,-1);
    cout<<ans<<endl;

    return 0;
}

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

int main() {
    int64_t a, b, x;
    cin >> a >> b >> x;
    cout << b / x - (a % x ? a / x + 1 : a / x) + 1 << endl;
    return 0;
}

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

int main()
{
    int n;
    cin>>n;
    vector<int>a(n);

    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a.begin(),a.end());

    for(int i=0;i<n-1;i++)
    {
        if(a[i]==a[i+1])
        {
            cout<<"NO";
            exit(0);
        }
    }
    cout<<"YES";
    exit(0);
}


Measured memory_bytes: 4380
# import math
# import statistics
#a=input()
#b,c=int(input()),int(input())
# c=[]
# for i in a:
#    c.append(i)
e1,e2 = map(int,input().split())
#K = input()
# f = list(map(int,input().split()))
#g = [input() for _ in range(a)]
a=[2,3,4,5,6,7,8,9,10,11,12,13,1]
if e1==e2:
	print('Draw')
elif a.index(e1)>a.index(e2):
	print('Alice')
else:
	print('Bob')

Measured memory_bytes: 9104
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;cin>>s;
	string r_s=s;
	reverse(r_s.begin(),r_s.end());
	if(s==r_s){
		s=s.substr(0,s.size()/2);
		r_s=s;
		reverse(r_s.begin(),r_s.end());
		if(s==r_s) return 0*puts("Yes");
	}
	return 0*puts("No");
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

constexpr int MOD = 1000000007;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> PLL;

int N;
int a[100010];

int main() {
    cin >> N;
    for (int j = 0; j < N; ++j) {
        cin >> a[j];
        --a[j];
    }
    int count  = 0;
    for (int j = 0; j < N; ++j) {
        if (j == a[a[j]]) {
            ++count;
        }
    }
    cout << count/2 << endl;

    return 0;
}


Measured memory_bytes: 888
N, M, C = map(int, input().split())
B = list(map(int, input().split()))

# 解の個数
c = 0

for i in range(N):
    A = list(map(int, input().split()))
    a = 0
    for j in range(M):
        a += A[j] * B[j]
    if a + C > 0:
        c += 1
        
print(c)

Measured memory_bytes: 3060
// Created by code_sm
//
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp> 
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> pseudo_set;
#define ll long long
#define vi vector<int>
#define si set<int> 
#define mii map<int,int>
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define extract_word(s)  stringstream str(s); while(str>>word)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SET(s) cout<<fixed<<setprecision(s)
#define chotu 1000000007
#define set0(a) memset(a,0,sizeof(a))
#define endl "\n"
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define lower_string(s) transform(all(s),s.begin(),::tolower())
#define upper_string(s) transform(all(s),s.begin(),::toupper())
#define size(s) s.size()
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<typename T,typename U>
bool compare(T x,U y){return(abs(x-y)<=1e-9);}
void solve()
{
fastio
	int a,b;
cin>>a>>b;
  b--;
  a--;
int ans=ceil((float)b/a);
cout<<ans;
}
int main()
{
//code
fastio	
int t;
t=1;
while(t--)
{
	solve();
	cout<<endl;
}
}


Measured memory_bytes: 256
import scala.io.StdIn.{readInt,readLine}

object Main {
  def main(args:Array[String]) = {
    val n = readInt
    val players = new Array[Int](n)
    val a = for(i <- 1 to n) yield readLine.split(" ").map(_.toInt)
    for(i<-0 until 3) {
      { for(j<-0 until n) yield (a(j)(i),j) }.toList.groupBy(_._1).filter(_._2.length==1).foreach { p=>
        players(p._2(0)._2) += p._1
      }
    }
    players.foreach(println)
  }
}

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

int main () {
  long long time = 0;
  long long limit = 0;
  long long N, T;
  cin >> N >> T;
  long long t[N];
  for (long long i = 0; i < N; i++) {
    cin >> t[i];  
  } 
   
  for (long long i = 0; i < N; i++) {
    if (i == 0) {
      time =  T;  
      limit = T;
    }    
    else {
      if (limit <= t[i]) {
        time += T;
        limit = t[i] + T; 
      }    
      else {
        time  -= limit - t[i];
        time  += T;
        limit -= limit - t[i];
        limit += T;  
      }
    }
  }
  cout << time << endl;
}

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

long long N, M, A, B, X, Na[5005][5005], T[5005][5005], Y[5005][5005], i, j;

int main(){
  scanf("%lld%lld", &N, &M);
  for(i = 0; i < M; ++i){
    scanf("%lld%lld%lld", &A, &B, &X);
    ++T[A][B];
    --T[A + X + 1][B];
    --Y[A][B + 1];
    ++Y[A + X + 1][B + X + 2];
  }
  for(i = 1; i <= N; ++i){
    for(j = 1; j <= i; ++j){
      T[i][j] += T[i - 1][j];
    }
  }
  for(i = 1; i <= N; ++i){
    for(j = 1; j <= i; ++j){
      Y[i][j] += Y[i - 1][j - 1];
    }
  }
  B = 0;
  for(i = 1; i <= N; ++i){
    for(j = 1; j <= i; ++j){
      A = Y[i][j] + T[i][j];
      Na[i][j] = Na[i][j - 1] + A;
      if(Na[i][j])++B;
    }
  }
  /*for(i = 1; i <= N; ++i){
    cout << i << " : ";
    for(j = 1; j <= i; ++j){
      cout << T[i][j] << " ";
    }
    cout << endl;
  }
  for(i = 1; i <= N; ++i){
    cout << i << " : ";
    for(j = 1; j <= i; ++j){
      cout << Y[i][j] << " ";
    }
    cout << endl;
  }
  for(i = 1; i <= N; ++i){
    cout << i << " : ";
    for(j = 1; j <= i; ++j){
      cout << Na[i][j] << " ";
    }
    cout << endl;
  }*/
  cout << B << endl;
  return 0;
}

Measured memory_bytes: 353192
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let l = read_vec::<i64>();
    let mut ans = 0;
    for i in 0..n {
        for j in i + 1..n {
            for k in j + 1..n {
                if l[i] == l[j] || l[j] == l[k] || l[i] == l[k] {
                    continue;
                }
                let sum = l[i] + l[j] + l[k];
                let lmax = vec![i, j, k].into_iter().map(|x| l[x]).max().unwrap();
                let other = sum - lmax;
                if other > lmax {
                    ans += 1;
                }
            }
        }
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


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

typedef long long ll;
#define int ll
#define pb push_back
const int INF = 1e18;

signed main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n; cin>>n;
	int cost[n+1];
	for(int i=1;i<=n;i++)
		cin>>cost[i];

	vector<int> dp(n+1,INF);
	dp[1] = 0;

	for(int i=1;i<n;i++){
		dp[i+1] = min(dp[i+1], dp[i] + abs(cost[i+1]-cost[i]));
		if (i+2 <= n) dp[i+2] = min(dp[i+2],dp[i] + abs(cost[i+2]-cost[i]));
	}

	cout<<dp[n];
	return 0;
}

Measured memory_bytes: 1792
/*
 * main.c
 *
 *  Created on: 2019/03/30
 *      Author: family
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

char s[101] = {0};

int main()
{
    int N;
    int i = 0;
    int red = 0;
    scanf("%d", &N);
    scanf("%s", s);

    for(i = 0; i < N; i++) {
        if(s[i] == 'R') {
            red++;
        }
    }
    if((N - red) < red) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
	public static void main(String ar[])
	{
		Scanner sc = new Scanner(System.in);

		if (sc.nextInt() < 1200)
		{
			System.out.println("ABC");
		}
		else
		{
			System.out.println("ARC");
		}
	}
}


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

int main(){
  long long int n;
  cin >> n;
  if(n%11>6)cout <<n/11*2+2 <<endl;
  else if(n%11==0)cout << n/11*2<<endl;
  else cout << n/11*2+1 <<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;

const int MAX = 2000;

int main(){
    int H,W;
    char grid[MAX][MAX];
    int vcnt[MAX][MAX];
    int scnt[MAX][MAX];

    cin >> H >> W;
    for(int i = 0;i < H;i++){
        for(int j = 0;j < W;j++){
            cin >> grid[i][j];
            vcnt[i][j] = 0;
            scnt[i][j] = 0;
        }
    }

    for(int i = 0;i < H;i++){
        int pos = 0;
        int cnt = 0;

        for(int j = 0;j <= W;j++){
            if(grid[i][j] == '#' || j == W){

                for(int k = j - 1;k >= pos;k--){
                    scnt[i][k] = cnt;
                }
                pos = j;
                cnt = 0;
            }else{
                cnt++;
            }
        }
    }

    for(int i = 0;i < W;i++){
        int pos = 0;
        int cnt = 0;

        for(int j = 0;j <= H;j++){
            if(grid[j][i] == '#' || j == H){

                for(int k = j - 1;k >= pos;k--){
                    vcnt[k][i] = cnt;
                }
                pos = j;
                cnt = 0;
            }else{
                cnt++;
            }
        }
    }

    int ans = 0;
    for(int i = 0;i < H;i++){
        for(int j = 0;j < W;j++){
            ans = max(ans,scnt[i][j] + vcnt[i][j] - 1);
        }
    }

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

Measured memory_bytes: 35456
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define debug(x) cerr<<#x<<'='<<x<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int mod = 1000000007;
inline int mul(int x,int y){return 1ll*x*y%mod;}
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
int sq(int x){return 1ll*x*x%mod;}
int pow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(pow(a,b/2))) : sq(pow(a,b/2)));}
int inv(int a){return pow(a,mod-2);}
const int N = 200010;
int fac[N],invfac[N];
int C(int n,int m){return mul(fac[n],mul(invfac[m],invfac[n-m]));}
int ans = 0,a,b,c,n;
int main() {
	fac[0] = 1;
	for(int i=1;i<N;i++){
		fac[i] = mul(fac[i-1],i);
	}
	invfac[N-1] = pow(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--){
		invfac[i] = mul(invfac[i+1],i+1);
	}
	
	cin>>n>>a>>b>>c;
	a = mul(a,inv(100));
	b = mul(b,inv(100));
	c = mul(c,inv(100));
	int ych = inv(a+b);
	int ab = a+b;
	a = mul(a,inv(ab));
	b = mul(b,inv(ab));
	for(int i=n;i<n+n;i++){
		int ys = mul(ych,i);
		//cout<<ys<<endl;
		ans = add(ans,mul(ys,mul(C(i-1,n-1),mul(pow(a,n),pow(b,i-n)))));
		ans = add(ans,mul(ys,mul(C(i-1,n-1),mul(pow(b,n),pow(a,i-n)))));
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long
#define db double 

using namespace std;

const db pi = acos(-1.0); 
const int N = 3003; 

int n, L;
int a[N]; 
db X, Y; 

int main () {
  scanf("%d %d", &n, &L); 
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]); 
  }
  for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
      db t = 1.0 * (a[i] + a[j]) / L; 
      db x = cos(pi * t); 
      db y = sin(pi * t); 
      X += x * (2 * (j - i) - n), Y += y * (2 * (j - i) - n); 
    }
  }
  db P = 1.0 * n * (n - 1) * (n - 2) / 6; 
  printf("%.10lf %.10lf\n", -1.0 * X / P, -1.0 * Y / P); 
  return 0; 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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 long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	int n,k;
	cin >>n>>k;
	VVi a(2,Vi(n+1,0));
	Vi ans;
	rep(i,n){
		cin>>a[0][i];
	}
	int  last=0;
	int len=0;
	rep(i,k){
		len=0;
		rep(j,n){
			a[(i+1)%2][j]=0;
		}
		rep(j,n){
		//	clog << max(0, j - a[i % 2][j]) << " " << min(n, j + a[i % 2][j] + 1) << endl;
			a[(i+1)%2][max(0,j-a[i%2][j])]++;
			a[(i + 1) % 2][min(n, j + a[i % 2][j]+1)]--;
		}
		rep(j, n)
		{
		//	clog << a[(i + 1) % 2][j] <<" ";
			if (j != 0)
			{
				a[(i + 1) % 2][j] += a[(i + 1) % 2][j-1];
			}
			if (n == a[(i + 1) % 2][j]){
				len++;
			}
		}
	//	clog<<endl;
	//	clog<<len<<" "<<i<<endl;
		if(len==n or i==k-1){
			ans = a[(i + 1) % 2];
			break;
		}
	}
	rep(i,n){
		cout<<(ans[i]);
		if(i!=n-1){
			cout<<" ";
		}
	}
	cout<<endl;
}

Measured memory_bytes: 5684
#include<bits/stdc++.h>
using namespace std;
int hea[100010],nxt[200010],to[200010],d[100010],tot;
long long v[100010];
void fason(int x,int y)
{
	nxt[++tot]=hea[x];
	hea[x]=tot;
	to[tot]=y;
}
long long dfs(int x,int f,int fa)
{
	if(d[x]==1)return v[x];
	long long s=0;
	for(int i=hea[x];i;i=nxt[i])
	{
		int y=to[i];
		if(y==fa)continue;
		long long t=dfs(y,0,x);
		if(t==-1||t>v[x])return -1;
		s+=t;
	}
	if(f==1)return s==v[x]*2?1:-1;
	if(s>2*v[x]||v[x]-s>0)return -1;
	else return 2*v[x]-s;
}
int main()
{
	int n,x,y;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld",v+i);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		fason(x,y);
		fason(y,x);
		d[x]++;
		d[y]++;
	}
	if(n==2)
	{
		puts(v[1]==v[2]?"YES":"NO");
		return 0;
	}
	int rt;
	for(int i=1;i<=n;i++)
		if(d[i]>1)
		{
			rt=i;
			break;
		}
	if(dfs(rt,1,0)==1)puts("YES");
	else puts("NO");
	return 0;
}

Measured memory_bytes: 8704
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input =new BufferedReader (new InputStreamReader (System.in));
		String str = input.readLine( );
		String[] list = str.split(" ");
		int a = Integer.parseInt(list[0]);
		int b = Integer.parseInt(list[1]);
		String answer = "";

		if(a > b){
			if(b == 1){
				answer = "Bob";
			}else{
				answer = "Alice";
			}
		}else if(a == b){
			answer = "Draw";
		}else if(a < b){
			if(a == 1){
				answer = "Alice";
			}else{
				answer = "Bob";
			}
		}

		System.out.println(answer);

	}

}


Measured memory_bytes: 21204
import java.util.*;

class Main{
	public static void main(String[] $){
		Scanner s=new Scanner(System.in);
		int n=s.nextInt(),k=s.nextInt(),f[]=new int[n],dp[]=new int[n];
		Arrays.setAll(f,i->s.nextInt());
		Arrays.fill(dp,1,n,1000000000);
		for(int i=0;i<n;++i){
			for(int j=i+1,e=Math.min(n,i+k+1);j<e;++j)
				dp[j]=Math.min(
						dp[j],
						dp[i]+Math.abs(f[j]-f[i]));
		}
		System.out.println(dp[n-1]);
	}
}

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

int main()
{
    int n, d, ans = 0;
    cin >> n >> d;
    int a[10][10];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < d; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            int sum = 0;
            for (int k = 0; k < d; k++)
            {
                sum += (a[i][k] - a[j][k]) * (a[i][k]-a[j][k]);
            }
            int dist = sqrt(sum);
            if (dist*dist == sum)
                ans++;
        }
    }
    cout << ans;
    return 0;
}


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

using namespace std;

int main(void){
    int N,X;
    cin>>N>>X;
    vector<int> L(N);
    for(int i=0;i<N;i++){
        cin>>L[i];
    }
    int count;
    int result=0;
    for(count=0;;count++){
        result+=L[count];
        if(count==N) break;
        if(result>X) break;
    }
    cout<<count+1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,n) for(int i=0;i<(n);i++)
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
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;}
template<class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T LCM(T a,T b){return a/GCD(a,b)*b;}


int main(){
	int r;
  cin >> r;
  cout << r*r*3 << endl;
}

Measured memory_bytes: 256
N, D = list(map(int, input().split()))

cod = [0]*N

for i in range(N):
    x, y = list(map(int, input().split()))
    cod[i] = (x, y)

ans = 0
for i in range(N):
    x, y = cod[i]

    if (x**2 + y**2) <= D**2:
        ans += 1

print(ans)


Measured memory_bytes: 78944
#include <bits/stdc++.h>
using namespace std; 
#define max(a, b) (a < b ? b : a) 
#define min(a, b) ((a > b) ? b : a) 
#define mod 1e9 + 7 
#define FOR(a, c) for (int(a) = 0; (a) < (c); (a)++) 
#define FORL(a, b, c) for (int(a) = (b); (a) <= (c); (a)++) 
#define FORR(a, b, c) for (int(a) = (b); (a) >= (c); (a)--) 
#define INF 1000000000000000003 
typedef long long int ll; 
typedef vector<int> vi; 
typedef pair<int, int> pi; 
#define F first 
#define S second 
#define pb push_back 
#define POB pop_back 
#define MP make_pair 
int main() 
{ 
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll arr[3];
    arr[0]=a;
    arr[1]=b;
    arr[2]=c;
    ll temp=1;
    ll sum=0;
    for(int i=0;i<3;i++)
    {
    	if(k-arr[i]>0)
    	{
    		k=k-arr[i];
			sum=(sum)+(arr[i]*temp);
			temp--;	
		}
		else
		{
			sum=(sum)+(k*temp);
			cout<<sum<<endl;
			break;
		}
	}
     
    return 0; 
} 

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;++i)
#define all(v) v.begin(), v.end()
#define PI 3.141592653589793238462643383279
typedef long long int ll;
typedef unsigned long long ull;
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;}
typedef pair<ll,ll> P;
const long long MOD = 1e9+7;
const ll INF = 1LL << 60;

int main(){
    int n;
    cin >> n;
    vector<int>a(n);
    for(int i = 0; i < n; i++){
       cin >> a[i];
    }
    for(int i = n-1; i >= 0; i--){
        cout << a[i];
        if(i > 0){
            cout << " ";
        }
    }
    cout << endl;

}


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


int main() {
  long long N, A, B;
    long long C, a, b, ans;
  cin >> N >> A >> B;
  
  C = A + B;
  
  a = N / C;
  b = N % C;
  ans = a * A;
  if(b > A){
    ans += A;
  }
  else{
    ans += b;
  }
  
  cout << ans;
  
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}

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

  REP(i, S.size()) {
    S.at(i) = S.at(i) + N;
    if(S.at(i) - 0 >= 91) {
      S.at(i) = S.at(i) - 26;
    }
  }

  cout << S << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <algorithm>
#define REP(i, b) for (int i = 0 ; i < b ; i++ )
typedef long long ll;
using namespace std;

int main() {
    int H, N;
    cin  >> H >> N;
    ll INF = 1L<<50;
    ll dp[H+1];
    fill(dp, dp + (H+1), INF);
    dp[0]  = 0 ;
    for (int i = 0 ; i < N ; i ++ ) {
        int a, b ;
        cin >> a >> b;
        for (int j = 0 ; j < H ; j ++) {
            int ind = min(H, j+a);
            dp[ind] = min(dp[ind], dp[j] + b);
        }
    }
    cout << dp[H] << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000
#define ll long long
char s[MAX]; 
int main(){
	 ios_base::sync_with_stdio(false);
	  cin.tie(NULL);cout.tie(NULL);
	unsigned  ll n;
	 cin>>n;
	// f(n);
    unsigned ll i = 0;
    while (n > 0) {   
        ll r = n % 26; 
        if (r == 0) { 
            s[i++]='z'; 
            n = (n / 26) - 1; 
        } 
        else
        { 
            s[i++] = (r-1)+'a'; 
            n = n / 26; 
        } 
    } 
    s[i] = '\0'; 
    reverse(s,s+strlen(s));
 cout << s << endl;
}


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

#include <stdio.h>
#include <cctype>

int main(void)
{
	std::string st;
	getline(cin, st);
	
	
	
	for(int i = 0 ; i < st.size();i++ ){

		char ch = st[i];
		if (islower(ch)){	//?°?????????????
			ch = toupper(ch);		//??§????????§??????
		}
		else if (isupper(ch)){
			ch = tolower(ch);
		}
		else {
			//????????????
		}
		printf("%c", ch);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 1168
#include <bits/stdc++.h>
using namespace std;
struct fastio { fastio () { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } _io;
template<class T, class U> bool chmax(T& a, const U &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class U> bool chmin(T& a, const U &b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
	char c;
	cin >> c;
	if (islower(c)) {
		cout << 'a' << '\n';
	} else {
		cout << 'A' << '\n';
	}
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int a[N];
int main ()
{
int n,max1=-123112123,min1=123112123,i;
cin >> n;
for (i=1;i<=n;i++)
{
	cin >> a[i];
	if (a[i]<min1)min1=a[i];
	if (a[i]>max1)max1=a[i];
}
cout << max1-min1;

return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <deque>
#include <string.h>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
ll MOD = 1000000007;


int main(){
  int n;
  cin >> n;
  if(n == 3 || n == 5 || n == 7) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

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

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

string s;
ll dp[100100][2];

int main(void){
	int n,i;
	cin >> s;
	n = s.l_ength();
	dp[0][1] = 1ll;
	for(i=0; i<n; ++i){
		if(s[i]=='1'){
			add_mod(dp[i+1][1],(dp[i][1]*2)%MOD);
			add_mod(dp[i+1][0],dp[i][1]);
		}else{
			add_mod(dp[i+1][1],dp[i][1]);
		}
		add_mod(dp[i+1][0],(dp[i][0]*3)%MOD);
	}
	cout << ((dp[n][0]+dp[n][1])%MOD) << endl;
	return 0;
}


Measured memory_bytes: 2048
import collections
n = int(input())
a = [int(i) for i in input().split()]
x,answer = collections.Counter(a),0
for i in range(min(a),max(a)+1):
	num = 0
	for j in range(i-1,i+2):
		try:
			num += x[j]
		except:
			pass
	if num>answer:
		answer = num
print(answer)


Measured memory_bytes: 14564
import math

class Point():
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

def koch(d, p1, p2):
    if d == 0:
        return

    else:
        s = Point()
        t = Point()
        u = Point()

        s.x = (2*p1.x + 1*p2.x)/3.0
        s.y = (2*p1.y + 1*p2.y)/3.0

        t.x = (1*p1.x + 2*p2.x)/3.0
        t.y = (1*p1.y + 2*p2.y)/3.0

        u.x = s.x + math.cos(math.radians(60)) * (t.x - s.x) - math.sin(math.radians(60)) * (t.y - s.y)
        u.y = s.y + math.sin(math.radians(60)) * (t.x - s.x) + math.cos(math.radians(60)) * (t.y - s.y)

        koch(d - 1, p1, s)
        print(s.x, s.y)
        koch(d - 1, s, u)
        print(u.x, u.y)
        koch(d - 1, u, t)
        print(t.x, t.y)
        koch(d - 1, t, p2)

def main():
    n = int(input())

    p1 = Point(0, 0)
    p2 = Point(100, 0)

    print(p1.x, p1.y)
    koch(n, p1, p2)
    print(p2.x, p2.y)

main()


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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

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

int main(int argc, char *argv[]) {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    ll A, B, C, D;
    cin >> A >> B >> C >> D;

    A--;

    ll ac = A - A/C, ad = A - A/D, acd = A - A/lcm(C, D);

    ll bc = B - B/C, bd = B - B/D, bcd = B - B/lcm(C, D);

    cout << bc + bd - bcd - (ac + ad - acd) << endl;
    return 0;
}

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

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

int n, m;

//
// Union-Find
//
const int MAX_N = 200010;
int par[MAX_N], rnk[MAX_N];

// n要素で初期化
void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i; rnk[i] = 0;
    }
}

// 木の根を求める
int find(int x) {
    if(par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

// x と y の属する集合を併合
void unite(int x, int y) {
    x = find(x); y = find(y);
    if(x == y) return ;

    if(rnk[x] < rnk[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if(rnk[x] == rnk[y]) rnk[x]++;
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

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

    rep(i,n){
        int k; scanf("%d", &k);
        vector<int> lan;
        rep(j,k){
            int l; scanf("%d", &l);
            --l;
            unite(i, n + l);
        }
    }

    rep(i,n) {
        if(!same(0,i)) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;

    return 0;
}

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

int n,c;
int D[31][31], C[31][3];
long long ans=1000*500*500;

int main(){
	cin>>n>>c;
	for(int i=1;i<=c;i++){
		for(int j=1;j<=c;j++){
			cin>>D[i][j];
		}
	}
	for(int i=1;i<=c;i++){
		for(int j=1;j<=c;j++){
			C[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int tmp;
			cin>>tmp;
			C[tmp][(i+j)%3]++;
		}
	}
	long long tmp=0;
	for(int i=1;i<=c;i++){
		for(int j=1;j<=c;j++){
			for(int k=1;k<=c;k++){
				if(i!=j and j!=k and i!=k){
					tmp=0;
					for(int l=1;l<=c;l++){
						tmp+=C[l][0]*D[l][i];
					}
					for(int l=1;l<=c;l++){
						tmp+=C[l][1]*D[l][j];
					}
					for(int l=1;l<=c;l++){
						tmp+=C[l][2]*D[l][k];
					}
					//cout<<ans<<endl;
					ans=min(ans,tmp);
				}
			}
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()

const string YES = "Yes";

int main(){
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> net(n);
    REP(i, m){
        ll ai, bi;
        cin >> ai >> bi;
        ai--; bi--;
        net.at(ai).push_back(bi);
        net.at(bi).push_back(ai);
    }

    vector<ll> sign(n, -1);
    vector<ll> dist(n, -1);
    sign.at(0) = 0;
    dist.at(0) = 0;
    queue<ll> que;
    que.push(0);
    while(!que.empty()){
        ll cur = que.front(); que.pop();
        for(ll nxt : net.at(cur)){
            if(dist.at(nxt) != -1){ continue; }
            dist.at(nxt) = dist.at(cur) + 1;
            sign.at(nxt) = cur;
            que.push(nxt);
        }
    }

    cout << YES << endl;
    for(ll i = 1; i < n; ++i){
        cout << sign.at(i) + 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 13640
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

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

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  int n;
  cin >> n;
  string s = to_string(n);

  int a = 0;
  REP(i, s.size()) a += s[i] -'0';

  if(n%a == 0) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct Opt{
	int opt,x,y,z;
	Opt(){}
	Opt(int _o,int _x,int _y,int _z){
		opt=_o;x=_x;y=_y;z=_z; 
	}
}a[200005];int tot;
int pw[205],bit[205][2],cnt;
void Pw(){
	a[++tot]=Opt(1,0,3,3);
	a[++tot]=Opt(1,1,3,3);
	a[++tot]=Opt(1,3,3,3);
	a[++tot]=Opt(0,1,3,3);
	cnt=3;pw[0]=3;
	for(int i=1;i<32;++i)
		pw[i]=++cnt,a[++tot]=Opt(1,pw[i-1],pw[i-1],pw[i]);
}
void apart(int type){//type= A or B?
	a[++tot]=Opt(1,type,pw[0],type);
	int sum=++cnt;
	for(int i=31;i>=0;--i){
		int res=++cnt;
		a[++tot]=Opt(1,sum,pw[i],res);// res = sum + 2^i
		a[++tot]=Opt(0,res,type,res); // res < type ?
		bit[i][type]=res; // (type>>i)&1
		++cnt; a[++tot]=Opt(1,res,cnt,cnt);
		for(int j=1;j<=i;++j) a[++tot]=Opt(1,cnt,cnt,cnt);
		a[++tot]=Opt(1,sum,cnt,sum);
	}
}
int main(){
	//freopen("1.out","w",stdout);
	Pw();apart(0),apart(1);
	for(int i=0;i<32;++i)
		for(int j=0;j<32;++j){
			int res=++cnt;
			a[++tot]=Opt(1,bit[i][0],bit[j][1],res);
			a[++tot]=Opt(0,pw[0],res,res);
			for(int k=1;k<=i+j;++k)
				a[++tot]=Opt(1,res,res,res);
			a[++tot]=Opt(1,res,2,2);
		}
	cout<<tot<<endl;
	for(int i=1;i<=tot;++i)
		cout<<((a[i].opt==1)?"+":"<")<<" "<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<endl;
	return 0;
}

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

using namespace std;

char s[500];
char y[] = "YAKI";

int main() {
  scanf("%s", s);
  int n = strlen(s);
  bool ok = 1;
  for (int i = 0; i < 4; i++)
    ok &= y[i] == s[i];
  puts(ok ? "Yes" : "No"); 
  return 0;
}

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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

int main() {
  string s;
  cin >> s;
  cout << count(s.begin(), s.end(), '1') << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    double w, h, x, y;
    cin >> w >> h >> x >> y;

    bool jud = false;

    if(w/2 == x && h/2 == y) jud = true;

    if(jud){
        cout << w*h/2.0 << " " << 1 << endl;
    }

    else{
        cout << w*h/2.0 << " " << 0 << endl;
    } 
}

    

    

Measured memory_bytes: 256