akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <bitset>
using namespace std;
const int N=2005;
int n;
int a[N],asum;
bitset<(1<<22)> f;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		asum+=a[i];
	}
	f[0]=1;	
	for(int i=1;i<=n;i++)
		f|=f<<a[i];
	for(int i=(asum+1)>>1;i<=asum;i++)
		if(f[i]){
			printf("%d\n",i);
			break;
		}
	return 0;
}

Measured memory_bytes: 1664
x,n=map(int,input().split())
if n==0:
    print(x)
    exit()
List=list(map(int,input().split()))
ans=list(range(0,102))
min_num=1000
for i in List:
    ans.remove(i)
for i in ans:
    if(abs(i-x)<abs(min_num-x)) or (abs(i-x)==abs(min_num-x) and i<min_num):
        min_num=i
print(min_num)

Measured memory_bytes: 9220
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(W: int, H: int, x: int, y: int):
    S = W * H / 2
    f = int((W == 2 * x) and (H == 2 * y))
    return "{} {}".format(S, f)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    W = int(next(tokens))  # type: int
    H = int(next(tokens))  # type: int
    x = int(next(tokens))  # type: int
    y = int(next(tokens))  # type: int
    result = solve(W, H, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<ll,pair<ll,char>>
#define sorted(a_1) sort(a_1.begin(),a_1.end())
#define rsorted(a_1) sort(a_1.rbegin(),a_1.rend())
#define t1(a_1) cout<<a_1<<endl;
#define t2(a_1) for(auto it_test : a_1) cout<<it_test<<" ";
#define MOD 1000000007

ll dp[101][100001];
ll topDown(vector<ll>&arr, ll index, ll k){
    if(k==0) return 1LL;
    if(index<0) return 0LL;
    if(dp[index][k]>=0) return dp[index][k];
    ll ways = 0;    
    for(ll i=min(arr[index],k);i>=0;i--){
        ways+=topDown(arr,index-1, k-i)%MOD;
        ways%=MOD;
    }
    dp[index][k] = ways;
    return ways;
}
void solve(){
    ll n,k;
    cin>>n>>k;
    vector<ll>arr(n),cnt(n+1,0);
    for(auto &i : arr) cin>>i;
    memset(dp,0,sizeof(dp));
    // ll ans = topDown(arr,n-1,k);
    // t1(ans)
    dp[0][0] = 1;
    for(int i=1;i<=k;i++) dp[0][i] += dp[0][i-1];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            if(j-arr[i-1]>0){
                dp[i][j] = ((dp[i-1][j]%MOD - dp[i-1][j-arr[i-1]-1]%MOD) + MOD)%MOD;
            }
            else
                dp[i][j] = dp[i-1][j]%MOD;
        }
        for(int j=1;j<=k;j++) {
            dp[i][j]+=dp[i][j-1];
            dp[i][j]%=MOD;
        }
    }

    t1((dp[n][k] - dp[n][k-1]+MOD)%MOD);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    while(t--){
        solve();
    }

return 0;
}

Measured memory_bytes: 82544
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int dp[100005];
int func(int index){
    if(index==n-1)
        return 0;
if(dp[index]!=-1)
return dp[index];
int left=abs(a[index]-a[index+1])+func(index+1);
int right=1e18+10;
if(index+2<n)
    right=abs(a[index]-a[index+2])+func(index+2);
return dp[index]= min(left,right);
}
int main(){
cin >>n;
//int height[n];
for(int i=0;i<n;i++){
    cin >>a[i];
}
memset(dp,-1,sizeof(dp));
//vector<vector<int>>dp(n,vector<int>height(n,-1));
cout << func(0);
return 0;
}


Measured memory_bytes: 4096
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int main(){
    int n, m;
    cin >> n >> m;
    vector< pair<ll, int> > V(n, make_pair(0,0));
    REP(i, n) cin >> V[i].first >> V[i].second;
    sort(ALL(V));
    // REP(i,n) cout <<i << " "<< V[i].first << " " << V[i].second << endl;
    ll ans=0;
    REP(i,n){
        // cout << i << "にいて，もう " << m << "個かいたい．お金はまだ"<<ans << endl;
        if(m >= V[i].second ) {
            ans += V[i].first * V[i].second;
            m -= V[i].second;
        }
        else {
            ans+= V[i].first * m;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1920
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

struct po{
  int f,a,t,x,y;
};

int main() {

  int n;
  cin >> n;

  po D[101];
  for(int i=0;i<n;i++) cin >>D[i].f >> D[i].a >> D[i].t >> D[i].x >> D[i].y;

  for(int i=0;i<n;i++) 
    for(int j=n-1;j>i;i++) 
      if(D[i].f > D[i+1].f) {
	po t = D[i];
	D[i] = D[i+1];
	D[i+1] = t;
      } 

  int ans[2] = {-1,-1};
  int time[2] ={};

  for(int i=0;i<n-1;i++) {
    if(D[i].t == D[i+1].t && D[i].a != D[i+1].a){
      int dis = (D[i+1].x-D[i].x)*(D[i+1].x-D[i].x)+(D[i+1].y-D[i].y)*(D[i+1].y-D[i].y);
	if(ans[D[i].t] < dis) {
	  ans[D[i].t] = dis;
	  time[D[i].t] = D[i+1].f - D[i].f;
	}else if(ans[D[i].t] == dis && time[D[i].t] > D[i+1].f-D[i].f) time[D[i].t] = D[i+1].f- D[i].f;
    }
  }

  if(ans[0] !=-1) printf("%.9lf %.9lf\n",sqrt(ans[0]),time[0]/60.0);
  else cout << -1 <<" " << -1 << endl;

  if(ans[1] !=-1) printf("%.9lf %.9lf\n",sqrt(ans[1]),time[1]/60.0);
  else cout << -1 <<" " << -1 << endl;

  return 0;
}

Measured memory_bytes: 1248
H, W, M = map(int, input().split())
countH = [0 for h in range(H)]
countW = [0 for w in range(W)]
Bh = {}

for i in range(M):
  h, w = map(int, input().split())
  h, w = h-1, w-1
  if h in Bh:
    Bh[h].add(w)
  else:
    Bh[h] = {w}
  countH[h] += 1
  countW[w] += 1

maxh = 0
ch = []
maxw = 0
cw = []
for i in range(H):
  if maxh==countH[i]:
    ch.append(i)
  elif maxh<countH[i]:
    ch = [i]
    maxh = countH[i]
for i in range(W):
  if maxw==countW[i]:
    cw.append(i)
  elif maxw<countW[i]:
    cw = [i]
    maxw = countW[i]

#print(countH)
#print(countW)
#rint(Bh)
ans = maxh + maxw
flag = False
for h in ch:
  for w in cw:
    #print(h,w)
    if w not in Bh[h]:
      flag = True
      break
if flag:
  print(ans)
else:
  print(ans-1)

Measured memory_bytes: 213784
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 
using ll = long long;
 
const int nax = 10123;
char k[nax];
const int mod = 1e9 + 7;
 
void add_self(int& a, int b) {
    a += b;
    if(a >= mod) {
        a -= mod;
    }
}
 
int modder(int x, int moddi)
{
	if (x >= moddi)
        return x % moddi;
    return x;
}
 
int main() {
    scanf("%s", k);
    int D;
    scanf("%d", &D);
    int len = strlen(k);
    vector<array<int,2>> dp(D, array<int,2>{});
    vector<array<int,2>> new_dp(D, array<int,2>{});
    // dp[sum][smaller_already] - the number of ways to choose digits so far
    // such that the sum of digits modulo D is 'sum' and 'smaller_already'
    // says whether we already chosen some digit smaller than in K
    dp[0][0] = 1;
    for(int where = 0; where < len; ++where) {
        fill(new_dp.begin(), new_dp.end(), array<int,2>{});
        for(int sum = 0; sum < D; ++sum) {
            int sum2 = sum % D;
            for(bool sm_already : {false, true}) {
                for(int digit = 0; digit < 10; ++digit) {
                    if(digit > k[where] - '0' && !sm_already) {
                        break;
                    }
                    add_self(new_dp[modder(sum2+digit,D)][sm_already || (digit < k[where]-'0')],
                        dp[sum][sm_already]);
                }
            }
        }
        swap(dp, new_dp);
    }
    int answer = (dp[0][false] + dp[0][true]) % mod;
    --answer;
    if(answer == -1) {
        answer = mod - 1;
    }
    printf("%d\n", answer);
}

Measured memory_bytes: 256
a, b, c, d, e = list(int(input()) for i in range(5))

round = []
edge = []

for i in (a, b, c, d, e):
    if i % 10 == 0:
        round.append(0)
    else:
        edge.append(i % 10)

if len(edge) != 0:
    m = min(edge)
else:
    m = 10

ans = 0
for i in (a, b, c, d, e):
    ans += (i - 1) // 10 + 1

ans *= 10
ans -= (10 - m)
print(ans)


Measured memory_bytes: 3064
#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int N, A[222222];

long long compute(long long b)
{
  long long s = 0;

  for (int i = 0; i < N; i ++)
    s += std::abs(b + i - A[i]);

  return s;
}


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  std::cin >> N;

  for (int i = 0; i < N; i ++)
    std::cin >> A[i];

  long long l = -INF, u = INF;

  while (u - l > 1) {
    long long m = (l + u) / 2;

    (compute(m) < compute(m - 1) ? l : u) = m;
  }

  std::cout << compute(l) << std::endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int INF = (1 << 30) - 1;
int dsum(int n)
{
    int sum = 0;
    while ( n > 0 ) {
        sum += n % 10;
        n /= 10;
    }
    return ( sum );
}
int main()
{
    int N;
    int minv = INF;
    cin >> N;
    for ( int i = 1; i <= N / 2; i++ ) {
        int j = N - i;
        minv = min(minv, dsum(i) + dsum(j));
    }
    cout << minv << endl;
    return ( 0 );
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    int n;
    cin >> n;
    int d = n%10;
    if(d==3)
        printf("b");
    else if(d==0||d==1||d==6||d==8)
    printf("p");
    else
        printf("h");
    printf("on\n");

    return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ

//a^n modをO(logN)で計算
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main(){
    int64_t n,a,b;
    cin>>n>>a>>b;
    int64_t ans=modpow(2,n,big)-1;
    //cout<<ans<<endl;
    int64_t cha = 1,moa = 1;
    int64_t chb = 1,mob = 1;
    bool block=true;
    //cout<<(a%big)*(modpow(b,big-2,big)%big)%big<<endl;
    rep(i,a){
        cha = cha*(n-i)%big;
        cha = (cha%big) * (modpow(a-i,big-2,big)%big) % big;
    }
    /*
    rep(i,a){
        cha = (cha%big) * (modpow(a-i,big-2,big)%big) % big;
    }
    */
    //cout<<cha<<" "<<moa<<endl;
    rep(i,b){
        chb = chb*(n-i)%big;
        chb = (chb%big) * (modpow(b-i,big-2,big)%big) % big;   
    }
    /*
    rep(i,b){
        chb = (chb%big) * (modpow(b-i,big-2,big)%big) % big;   
    }
    */
    //cout<<chb<<" "<<mob<<endl;
    ans = ans-cha;
    if(ans<0){
        ans += big;
    }
    ans = ans -chb;
    if(ans<0){
        ans += big;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>
#include<functional>

using namespace std;
typedef long long int ll;

#define C cout<<
#define E <<endl

ll n,m,a,b,c,x,y,z,aa[100010],ba[100010];
bool r,ra,rb,rc;
string s,sa,sb,sc;
char ca,cb,cc[1000][1000],cd[1000][1000];
vector<ll> va,vb,vc;

int main(){
    cin>>n>>s;
    a=0;
    m=0;
    for(ll i=0;i<s.size();i++){
        a+=(s[i]=='I' ? 1:-1);
        m=max(a,m);
    }
    C m E;
}

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

using namespace std;

int main(){
    int n, b, f, r, v;
    cin >> n;
    vector <vector <int> > b1(3, vector<int>(10));
    vector <vector <int> > b2(3, vector<int>(10));
    vector <vector <int> > b3(3, vector<int>(10));
    vector <vector <int> > b4(3, vector<int>(10));
    for (int i=0; i<n; i++){
        cin >> b >> f >> r >> v;
        if(b == 1) b1.at(f-1).at(r-1) += v;
        else if(b == 2) b2.at(f-1).at(r-1) += v;
        else if(b == 3) b3.at(f-1).at(r-1) += v;
        else if(b == 4) b4.at(f-1).at(r-1) += v;
    }

    // b1
    for(int i=0; i<3; i++){
        for(int j=0; j<10; j++){
            cout << " " << b1.at(i).at(j);
        }
        cout << endl;
    }

    for(int sh=0; sh<20; sh++){
        cout << "#";
    }
    cout << endl;
    
    // b2
    for(int i=0; i<3; i++){
        for(int j=0; j<10; j++){
            cout << " " << b2.at(i).at(j);
        }
        cout << endl;
    }
    
    for(int sh=0; sh<20; sh++){
        cout << "#";
    }
    cout << endl;

    // b3
    for(int i=0; i<3; i++){
        for(int j=0; j<10; j++){
            cout << " " << b3.at(i).at(j);
        }
        cout << endl;
    }
    
    for(int sh=0; sh<20; sh++){
        cout << "#";
    }
    cout << endl;
    
    // b4
    for(int i=0; i<3; i++){
        for(int j=0; j<10; j++){
            cout << " " << b4.at(i).at(j);
        }
        cout << endl;
    }

    return 0;
}



Measured memory_bytes: 3164
local n, k, l = io.read("*n", "*n", "*n")

local function uf_initialize(n)
  local parent = {}
  for i = 1, n do parent[i] = i end
  return parent
end

local function uf_findroot(idx, parent)
  local idx_update = idx
  while parent[idx] ~= idx do
    idx = parent[idx]
  end
  while parent[idx_update] ~= idx do
    parent[idx_update], idx_update = idx, parent[idx_update]
  end
  return idx
end

local p1, p2 = uf_initialize(n), uf_initialize(n)

for i = 1, k do
  local a, b = io.read("*n", "*n")
  local ra, rb = uf_findroot(a, p1), uf_findroot(b, p1)
  p1[b], p1[rb] = ra, ra
end

for i = 1, l do
  local a, b = io.read("*n", "*n")
  local ra, rb = uf_findroot(a, p2), uf_findroot(b, p2)
  p2[b], p2[rb] = ra, ra
end

local function getidx(r1, r2)
  return r1 - 1 + r2 * n
end
local groups = {}
for i = 1, n do
  local idx = getidx(uf_findroot(i, p1), uf_findroot(i, p2))
  if not groups[idx] then
    groups[idx] = 1
  else
    groups[idx] = groups[idx] + 1
  end
end
for i = 1, n do
  local idx = getidx(uf_findroot(i, p1), uf_findroot(i, p2))
  io.write(groups[idx])
  io.write(i == n and "\n" or " ")
end


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

int main () {
  int K, S;
  cin >> K >> S;
 
  rep(x, K+1){
    rep(y ,K+1){
    //int z = S - x - y; 枚数のはなしなのにSにしている
    int z = K - x - y ; 
    // if (1000z + 5000y + 10000x == S){  *を忘れている！！
      if (10000*x + 5000*y + 1000*z == S && z >= 0){ //z>=0でなければいけない
        cout << x << " " << y << " " << z << endl;
      return 0; //returnしてなかったらcoutでif,elseの分岐が必要
    }
    /*
    else;{
      cout << "-1 -1 -1" << endl;   
    }
    */
    }
 }
  cout << "-1 -1 -1" << endl;
}

Measured memory_bytes: 256
type ABC(stream:System.IO.TextReader) =
  member this.Scan1 f = stream.ReadLine() |> f
  member this.Scan2 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1]))
  member this.Scan3 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1], a.[2]))
  member this.Scan4 f = stream.ReadLine().Split() |> Array.map f |> (fun a -> (a.[0], a.[1], a.[2], a.[3]))
  member this.ScanVecH f = stream.ReadLine().Split() |> Array.map f
  member this.ScanVecV n f = [| for i in 1..n -> stream.ReadLine() |> f |]
  member this.ScanMatrix n f  = [| for i in 1..n -> stream.ReadLine().Split() |> Array.map f |]
  member this.ScanCharMatrix n = [| for i in 1..n -> stream.ReadLine().ToCharArray() |]
  member this.Close () = stream.Close()

let util = ABC(stdin)

let L, R = util.Scan2 int

if (R-L >= 2020) // for safety. not sure the boundary 
then
  printfn "0"
else
  [ for i in L..R do
    for j in i+1..R do
      yield ((i % 2019) * (j % 2019)) % 2019
  ]
  |> List.min
  |> printfn "%d"

util.Close()


Measured memory_bytes: 80276
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  double sum = 0;
  int sum2 = 0;
  rep(i,n) sum += (double)a[i];
  double ave = sum/(double)n;
  rep(i,n) sum2 += a[i];
  int ave2 = sum2/n;
  int real_ave;
  if(ave-(double)ave2>=0.5) real_ave = ave2 + 1;
  else real_ave = ave2;
  int ans = 0;
  rep(i,n){
    ans += pow(a[i]-real_ave, 2);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	const maxWord = (1 << 30)
	buf := []byte{}
	sc.Buffer(buf, maxWord)
	sc.Split(bufio.ScanWords)
}

func input() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	a, _ := strconv.Atoi(input())
	b, _ := strconv.Atoi(input())
	strconv.Atoi(input())
	k, _ := strconv.Atoi(input())
	if k%2 == 0 {
		fmt.Println(a - b)
	} else {
		fmt.Println(b - a)
	}
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N][N];
  int main()
{  
    int t,n,m;
    cin>>n;
    int flag=0;
    for(int i=0;i<=n/4;i++)
    {
        m=n;
        m-=4*i;
        if(!m)flag=1;
        for(int j=0;j<=m/7;j++)
        {
            t=m;
            t-=7*j;
            if(!t)flag=1;
        }
    }
    if(flag)cout<<"Yes";
    else cout<<"No";
    
        
    return 0;
}

Measured memory_bytes: 3620
import java.io.*;
import java.util.*;

/**
 * @author masayamatu
 * 
 */
public class Main {
  
  public static void main(String[] args) throws IOException{
    FastScanner sc = new FastScanner();
    int n = sc.nextInt();
    long k = sc.nextLong();
    long[] A = new long[n];
    long gyaku = 0;
    long ans1 = 0;
    long ans2 = 0;
    long jun = 0;
    for(int i = 0; i < n; i++) {
      A[i] = sc.nextInt();
    }
    for(int i = 0; i < n; i++) {
      for(int j = i+1; j < n; j++) {
        if(A[i] > A[j]) {
          gyaku++;
        }else if(A[i] < A[j]) {
          jun++;
        }
      }
    }
    ans1 = (gyaku*k)%1000000007;
    ans2 = ((gyaku+jun)%1000000007)*((k*(k-1))/2%1000000007);
   
    System.out.println((ans1+ans2)%1000000007);
 }
 
}
class FastScanner {
  private final InputStream in = System.in;
  private final byte[] buffer = new byte[1024];
  private int ptr = 0;
  private int buflen = 0;
  private boolean hasNextByte() {
      if (ptr < buflen) {
          return true;
      }else{
          ptr = 0;
          try {
              buflen = in.read(buffer);
          } catch (IOException e) {
              e.printStackTrace();
          }
          if (buflen <= 0) {
              return false;
          }
      }
      return true;
  }
  private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
  private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
  public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
  public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while(isPrintableChar(b)) {
          sb.appendCodePoint(b);
          b = readByte();
      }
      return sb.toString();
  }
  public long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
          minus = true;
          b = readByte();
      }
      if (b < '0' || '9' < b) {
          throw new NumberFormatException();
      }
      while(true){
          if ('0' <= b && b <= '9') {
              n *= 10;
              n += b - '0';
          }else if(b == -1 || !isPrintableChar(b)){
              return minus ? -n : n;
          }else{
              throw new NumberFormatException();
          }
          b = readByte();
      }
  }
  public int nextInt() {
      long nl = nextLong();
      if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
      return (int) nl;
  }
  public double nextDouble() { return Double.parseDouble(next());}
}

Measured memory_bytes: 23252
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <limits>
#include <cmath>
#include <cassert>

using namespace std;
using ll = long long;

const int INF = 1<<30;
const int MOD = (int)1e9 + 7;
const int MAX_N = (int)1e5 + 5;
#define debug(x) cout << #x << ": " << x << endl

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t;
    while(cin >> t, t)
    {
        int n; cin >> n;
        for(int i = 0; i < n; i++)
        {
            int s, f; cin >> s >> f;
            t -= f - s;
        }
        if(t <= 0) cout << "OK" << endl;
        else cout << t << endl;
    }
    return 0;
}




Measured memory_bytes: 3128
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll x,y,k;
    cin>>x>>y>>k;
    cout<<y/k-x/k+(x%k==0)<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
c = input()

w = [0]*(n+1)
r = [0]*(n+1)
for i in range(0,n):
  w[i+1] = w[i]
  r[n-i-1] = r[n-i]
  if c[i]=='W':
    w[i+1] += 1
  if c[n-i-1]=='R':
    r[n-i-1] += 1

print(min([w[i]+r[i]-min(w[i],r[i]) for i in range(0,n+1)]))


Measured memory_bytes: 26784
#include <bits/stdc++.h>
using Int = int64_t;
using UInt = uint64_t;
using C = std::complex<double>;
#define rep(i, n) for(Int i = 0; i < (Int)(n); ++i)
#define guard(x) if( not (x) ) continue;
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif

int main() {
   Int n;
   std::cin >> n;
   std::vector<Int> ss(n-1), ts(n-1), ws(n-1);
   rep(i, n-1) std::cin >> ss[i] >> ts[i] >> ws[i];
   std::vector<std::vector<std::pair<Int,Int>>> nexts(n);
   rep(i, n-1) {
      Int s = ss[i], t = ts[i], w = ws[i];
      nexts[s].emplace_back(t, w);
      nexts[t].emplace_back(s, w);
   }
   std::vector<Int> xs(n, -1);
   std::function<void(Int,Int)> dfs = [&](Int i, Int prev) {
      for(auto kw : nexts[i]) {
         Int k, w; std::tie(k, w) = kw;
         guard( k != prev );
         xs[k] = xs[i] + w;
         dfs(k, i);
      }
   };
   Int a = 0;
   for(Int t = 0; t < 2; ++t) {
      xs.resize(n, -1);
      xs[a] = 0;
      dfs(a, -1);
      rep(i, n) if( xs[a] < xs[i] ) a = i;
   }
   Int res = xs[a];
   printf("%ld\n", res);
}



Measured memory_bytes: 20704
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
#include<cctype>

#define rep(a,b) for(register int i=a;i<=b;i++)
#define red(a,b) for(register int i=a;i>=b;i--)
#define ULL unsigned long long
#define LL long long

using namespace std;

int a[1000],b[1000];
int main()
{
   int N,M,X,Y;
   cin>>N>>M>>X>>Y;
   int flag=1;
   int pre1,pre2;
   rep(1,N)
   {
   	 cin>>a[i];
   } 
   rep(1,M)
   {
   	 cin>>b[i];
   }
   sort(a+1,a+1+N);
   sort(b+1,b+1+M);
   pre1=a[N]+1;
   pre2=b[1];
   if(pre2>X&&pre1<=Y&&pre2>=pre1)
   {
   	cout<<"No War"<<endl;
   }
   else cout<<"War"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int a,b,c;
	a=0;
	b=0;
	c=0;
	for(int i=0;i<3;i++){
		if(s[i]=='a'){
			a++;
		}
		if(s[i]=='b'){
			b++;
		}
		if(s[i]=='c'){
			c++;
		}
	}
	if(a==1&&b==1&&c==1){
	cout<<"Yes"<<endl;
    }
    else{
		cout<<"No"<<endl;
	}
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>
#include <cassert>
#include<string>
using namespace std;
int main(){
	int a = 0, b = 0, c=0, d[100000], e[100000],f=0, count = 0;
	char ac,uc[100000];
	cin >>a>>b ;
	if(a%3==0||b%3==0||(a+b)%3==0){
		cout << "Possible" << endl;
	}
	else {
		cout << "Impossible" << endl;
	}
		return 0;
}

Measured memory_bytes: 256
n = int(input())
s = [""]*n
dp = [[] for i in range(n+1)]
plus = []
minas = []
pgomi = []
mgomi = []
kosu = 0
for i in range(n):
    s[i] = input()
    dp[i] = [0]*(len(s[i]) + 1)
    check = True
    kosu += len(s[i])
    moi = 0
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        moi += p
        dp[i][j+1] = dp[i][j] + p
    saisyo = min(dp[i])
    if saisyo >= 0:plus.append(i)
    elif saisyo == dp[i][-1]:minas.append(i)
    elif dp[i][-1] >= 0:pgomi.append([moi,i])
    else:mgomi.append([moi,i])
pgomi.sort(reverse = True)
mgomi.sort(reverse = True)
ruiseki = [0]*(10**6+5)
idx = 0
for i in plus + [v[1] for v in pgomi] + [v[1] for v in mgomi] + minas:
    for j in range(len(s[i])):
        p = 0
        if s[i][j] == '(':p = 1
        else:p = -1
        ruiseki[idx+1] = ruiseki[idx] + p
        idx += 1
check = True
for i in range(kosu):
    if ruiseki[i+1] < 0:
        check = False
        break
if check == False or ruiseki[kosu] != 0:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 294316
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
const int maxn=2000+10;
const int mod=1000000007;
int N,X;
long long D;
long long dp[maxn][maxn];
#define read Read
long long quick_pow(long long a, long long b) {
    long long ans = 1;
    a %= mod;
    while (b) {
        if (b % 2 == 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
long long C(long long n, long long m) {
    if (m > n)
        return 0;
    long long ans = 1;
    for (int i = 1; i <= m; i++) {
        long long a = (n + i - m ) % mod;
        long long b = i % mod;
        ans = ans * (a * quick_pow(b, mod - 2) % mod) % mod;
    }
    return ans;
}
long long lucas(long long n, long long m) {
    if (m == 0) return 1;
    return C(n % mod, m % mod) * lucas(n / mod, m / mod) % mod;
}
long long sum[maxn][maxn];
void add(int i, int j, long long v) {
    while (j <= N) {
        sum[i][j] = (sum[i][j] + v);
        if (sum[i][j] >= mod)
            sum[i][j] -= mod;
        j += (j) & (-j);
    }
}

long long read(int i, int j) {
    long long s = 0;
    while (j > 0) {
        s = (s + sum[i][j]);
        if (s >= mod)
            s -= mod;
        j -= (j) & (-j);
    }
    return s;
}
int main(){
	//init();
	while(scanf("%d%lld%d", &N,&D,&X)==3&&(N,D,X)){
		memset(dp,0,sizeof(dp));
		memset(sum,0,sizeof(sum));
		for(int j=1;j<X;++j){
			dp[1][j]=1;
			add(1,j,1);
		}
		for(int i=2;i<=N;++i){
			for(int j=i;j<=N;++j){
				dp[i][j]=(dp[i][j]+read(i-1,j-1)-read(i-1,max(i-2,j-X))+mod)%mod;
				add(i,j,dp[i][j]);
				/*for(int k=1;k<X&&k<=j&&(i-1)<=(j-k);++k){
					dp[i][j]+=dp[i-1][j-k];
					dp[i][j]%=mod;
				}*/
			}
		}
		long long ans=0;
		for(int i=1;i<=N&&i<=D;++i){
			ans=(ans+dp[i][N]*lucas(D,i)%mod)%mod;
		}
		printf("%lld\n", ans);
	}
		
    return 0;
}

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

#define endl "\n"
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define all(x) (x).begin(),(x).end()
#define rect return 0
#define pause cout << endl; system("pause")
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define sz(x) (int)(x).size()
#define Pi acos(-1.0)
#define bitcount __builtin_popcountll

#define TupleGet(name, index) std::get<(index)>(name)
#define FOR(a, b, c) for(int (a) = (b); (a) < (c); ++(a))
#define FORs(a, b, c) for(int (a) = (b); (a) <= (c); ++(a))
#define revFOR(a, b, c) for(int (a) = (b); (a) > (c); --(a))
#define revFORs(a, b, c) for(int (a) = (b); (a) >= (c); --(a))
#define foreach(it, a) for(auto it = (a).begin(); it != (a).end(); it++)

using namespace std;

// *** TYPEDEF'S, CONSTANTS AND FUNCTIONS *** //
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef vector<vector<int> > vvi;

/* |T| |I| |P| |S|
@ string abc = "abcdefghijklmnopqrstuvwxyz";
@ 'char' - 'a' ::: порядковый номер латинской буквы
@ 'digit' - '0' or 'digit' - 48 ::: (char) ---> (int)
@ 'A' = dec 65 'Z' = dec 90
  'a' = dec 97 'z' = dec 122
  '0' = dec 48 '9' = dec 57
@ Если страдает скорость ввода:
1) ios::sync_with_stdio(0);
   cin.tie(0);
2) юзать сканф
@ для стринга перевод i-того символа в другой регистр: a[i] = char (a[i] +- 32)  :::  32 == 'a' - 'A'
@ int n (m знаков) :::  n[1] = n / 10^(m-1) ; n[m] = n % 10 ; n[m-1] = (n % 100)/10 ; n[m-2] = (n % 1000)/100...
@ cout << fixed << setprecision(n) ::: n знаков после запятой, без "fixed" - всего n знаков
@ abs(x-y) < EPS ::: равентсво вещественных чисел x и y по точности EPS
@ x + EPS < y  или  x - EPS < y ::: сравнение больше-меньше для вещественных чисел по точности EPS
@ если цифру можешь записать из головы - так и пиши в программе, иначе - пиши ФОРМУЛУ
@ «экспонента» - целое число, показывающее, на сколько надо сдвинуть десятичную запятую в числе ::: 123e2 = 12300 , 123e-4 = 0.0123
@ если задача плохо решается при нумерации с единицы, иногда оказывается намного проще перейти к нумерации с нуля.
  Особенно задачах, где явно надо делить на равные части.
@ while(cin >>)  |||  while (getline(cin, )) ::: считывание, пока даются данные
@ ctrl+Z ::: конец файла в консоли
@ Глобальные массивы, чтобы не было ошибок; размер брать с запасом
@ Количество цифр N числа X в b-ичной записи, N = floor[ log[b](X) ] + 1
@ ios::sync_with_stdio(0); //ввод
@ cin.tie(0); cout.tie(0); //могут быть проблемы в интерактивных задачах (частый ввод-вывод)
*/

void B() {
    ll n, m;
    cin >> n >> m;

    vll a(n);
    for (auto &i : a) cin >> i;

    vll ps(n, a[0]);
    FOR(i,1,n)ps[i]=ps[i-1]+a[i];

    unordered_map<ll, ll> cnt;
    cnt[0] = 1;

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ans += cnt[ps[i] % m];
        cnt[ps[i] % m]++;
    }

    cout << ans;
}

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

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

vector<pair<int, char> > bubble_sort(vector<pair<int, char> > A)
{
    bool flag = 1;
    int i = 0; //未ソート部分先頭アドレス
    int n = A.size();
    for (i; flag; i++)
    {
        flag = 0;
        for (int j = n - 2; j >= i; j--)
        {
            if (A[j].first > A[j+1].first)
            {
                swap(A[j +1], A[j]);
                flag = 1;
            }
        }
    }
    return A;
}

//交換回数出力なし任意の要素数
void selection_sort(vector<pair<int, char> > &vec)
{
    int n = vec.size();
    int m;    //変数交換用
    int minj; //暫定的な最小値アドレス
    for (int j = 0; j < n - 1; j++)
    { //jは未ソート部分の先頭アドレス
        minj = j;
        for (int i = j + 1; i < n; i++)
        {
            if (vec[i].first < vec[minj].first)
            {
                minj = i;
            }
        }
        if (minj != j)
        {
            swap(vec[minj], vec[j]);
        }
    }
}


int main(){
int n;
cin>>n;
vector<pair<int, char> > p(n);
for(int i=0;i<n;i++){
    cin>>p[i].second>>p[i].first;
}

  
  
vector<pair<int, char> > A=bubble_sort(p);
for(int i=0;i<n;i++){
    if(i!=n-1){
    cout<<A[i].second<<A[i].first<<" ";
    }else{
        cout<<A[i].second<<A[i].first<<endl;
        cout<<"Stable"<<endl;
    }
}

selection_sort(p);
for(int i=0;i<n;i++){
    if(i!=n-1){
    cout<<p[i].second<<p[i].first<<" ";
    }else{
        cout<<p[i].second<<p[i].first<<endl;
    }
}

if(A!=p){
    cout<<"Not stable"<<endl;
}else{
    cout<<"Stable"<<endl;
}
}


  



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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; typedef pair<ll, ll> P;
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<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);}
const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
//template end



int main(){
    int n,l; scanf("%d%d",&n,&l);
    vector<P> a(n);
    rep(i,0,n)scanf("%d%d",&a[i].first,&a[i].second);
    sort(ALL(a));
    ll sum[100010]={},pre[100010]={};
    rep(i,0,n){
        int diff=i+1-a[i].first;
        if(a[i].second==0)diff*=-1;
        sum[i+1]=sum[i]+diff;
    }
    rrep(i,n-1,-1){
        int diff=l-n+i+1-a[i].first;
        if(a[i].second==0)diff*=-1;
        pre[i]=pre[i+1]+diff;
    }
    ll ans=0;
    rep(i,0,n+1)chmax(ans,sum[i]+pre[i]);
    printf("%lld\n",ans);
    return 0;
}


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

int main(){
    map<string,int> id;
    map<int,string> di;
    id["ld"] = 26;  di[26] = "ld";
    id["mb"] = 27;  di[27] = "mb";
    id["mp"] = 28;  di[28] = "mp";
    id["nc"] = 29;  di[29] = "nc";
    id["nd"] = 30;  di[30] = "nd";
    id["ng"] = 31;  di[31] = "ng";
    id["nt"] = 32;  di[32] = "nt";
    id["nw"] = 33;  di[33] = "nw";
    id["ps"] = 34;  di[34] = "ps";
    id["qu"] = 35;  di[35] = "qu";
    id["cw"] = 36;  di[36] = "cw";
    id["ts"] = 37;  di[37] = "ts";
    
    int cnt[38][38] = {};

    int n;
    cin >> n;
    string s;
    while(cin >> s){
        int pos = 0, bef = -1;
        while(pos < s.length()){
            int aft;
            if(pos+1 < s.length() && id.count(s.substr(pos,2)) > 0){
                aft = id[s.substr(pos,2)];
                pos += 2;
            }else{
                aft = s[pos]-'a';
                pos++;
            }
            if(bef != -1)   cnt[bef][aft]++;
            bef = aft;
        }
    }
    for(int i = 0; i < 38; i++){
        int j = 0;
        for(int k = 1; k < 38; k++){
            if(cnt[i][j] < cnt[i][k])   j = k;
        }
        if(i < 26)  cout << (char)('a'+i);
        else        cout << di[i];
        cout << " ";
        if(j < 26)  cout << (char)('a'+j);
        else        cout << di[j];
        cout << " " << cnt[i][j] << endl;
    }
    return 0;
}


Measured memory_bytes: 3140
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 998244353
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int main(){
  int N;cin>>N;
  vector<vector<int> > to(N),cost(N);
  rep(i,N-1){
    int a,b,w;
    cin>>a>>b>>w;
    a--;b--;
    to[a].push_back(b);cost[a].push_back(w);
    to[b].push_back(a);cost[b].push_back(w);
  }
  vector<int> ans(N,-1);
  queue<int> q;

  ans[0]=0;
  q.push(0);

  while(!q.empty()){
    int v=q.front();
    q.pop();
    rep(i,to[v].size()){
      int u=to[v][i];
      int w=cost[v][i];
      if(ans[u]!=-1) continue;
      ans[u]=(ans[v]+w)%2;
      q.push(u);
    }
  }
  rep(i,N) cout<<ans[i]<<endl;
}


Measured memory_bytes: 11904
#include <bits/stdc++.h>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <cstring>
	#include <chrono>
	#include <complex>
	#define endl "\n"
	#define ll long long int
	#define vi vector<int>
	#define vll vector<ll>
	#define vvi vector < vi >
	#define pii pair<int,int>
	#define pll pair<long long, long long>
	#define mod 1000000007
	#define mod2 998244353
	#define inf 1000000000000000001;
	#define all(c) c.begin(),c.end()
	#define sz(v) ((ll)(v).size())
	#define mp(x,y) make_pair(x,y)
	#define mem(a,val) memset(a,val,sizeof(a))
	#define eb emplace_back
	#define pb push_back
	#define f first
	#define s second
	#define dbg(a) cout<<#a<<" --> "<<(a)<<"\n";
	#define forn(i,n) for (ll i=0; i<(n); ++i)
	#define fornd(i,n) for (ll i=(n)-1; i>=0; --i)
	#define forab(i,a,b) for (ll i=(a); i<=(b); ++i)
	#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
	using namespace std;
	bool isPowerOfTwo(int x) {
    return x && (!(x & (x - 1)));
	}
	int takemod(int x) {
    return (x % mod + mod) % mod;
	}
 
	int fpow(int base, int power, int MOD) {
    int result = 1;
    base = base % MOD;
    while (power) {
        if (power & 1)
            result = (result * base) % MOD;
        base = (base * base) % MOD;
        power = power >> 1;
    }
    return result;
	}
 
	int modinv(int x) {return fpow(x, mod - 2, mod);}
	void solve()
	{
		ll n;
		cin>>n;
		vll pre(100010,0);
		//ll x=1,y=1;z=1;
		forab(x,1,100)
		{
			forab(y,1,100)
			{
				forab(z,1,100)
				{
					ll er=x*x+y*y+z*z+x*y+y*z+z*x;
					if(er>10000)
						continue;
					// if(x==y&&y==z)
					// {
					// 	pre[er]+=6;
					// }
					// if((x==y)||(x==z)||(y==z))
					// {
					// 	pre[er]+=1;
					// }
					// else if(x==y&&y==z)
					// {
					// 	pre[er]++;
					// }
					// else
					// {
					// 	pre[er]+=6;

					// }
					pre[er-1]++;
				}
			}
		}
		forn(i,n)
		{
			cout<<pre[i]<<endl;
		}
	}
	int main()
	{	
		#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		#endif
		fast_io;
		int T=1;
		//cin>>T;
		// cin.ignore(); must be there when using getline(cin, s)
		while(T--)
		{
			solve();
		}
		return 0;
	}


Measured memory_bytes: 3896
#include <cstdio>
#define INF 1e9
#define eps 1e-6
typedef long long ll;

int n, ans[100010];

inline int F(int x){
	return x * x;
}

int main(){

	scanf("%d", &n);
	for(int x = 1; (F(x) / 2) <= n; x++)
		for(int y = 1; F(x + y) / 2 <= n; y++)
			for(int z = 1; (F(x + y) + F(y + z) + F(z + x)) / 2 <= n; z++)
				ans[(F(x + y) + F(y + z) + F(z + x)) / 2]++;
	for(int i = 1; i <= n; i++)
		printf("%d\n", ans[i]);

	return 0;
}


Measured memory_bytes: 1720
/// Containers Start
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// C Header Files
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <math.h>
#include <stdio.h>
/// Containers End

using namespace std;

/// Math Start
#define PI acos(-1.0)
#define Pi 3.141592653589793
#define EPS (1e-7)
#define INF (0x3f3f3f3f)
/// Math End

/// Extra Start
#define nn '\n'
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007
#define sz(a) int((a).size())
#define space " "
#define All(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
/// Extra End

#define rep(i, n) for (int i = 0; i < n; i++)
#define Cini(a)                                                                \
    int a;                                                                     \
    cin >> a;
#define Cinii(a, b)                                                            \
    int a, b;                                                                  \
    cin >> a >> b;
#define Ciniii(a, b, c)                                                        \
    int a, b, c;                                                               \
    cin >> a >> b >> c;
#define Cins(s)                                                                \
    string s;                                                                  \
    cin >> s;
#define Cinss(s1, s2)                                                          \
    string s1, s2;                                                             \
    cin >> s1 >> s2;
#define Cinc(c)                                                                \
    char c;                                                                    \
    cin >> c;
/// Functions End


/// Debug Start
#define deb(x) cout << #x << ": " << x << endl
#define deb2(x, y) cout << #x << ": " << x << '\t' << #y << ": " << y << endl;
#define deb3(x, y, z)                                                          \
    cout << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": "   \
         << z << endl;
/// Debug End

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

/**>>>>>>>>>>>>>>>>>>> END <<<<<<<<<<<<<<<<<<**/

/// template


signed main(void) {
    cin.sync_with_stdio(false);
    cin.tie(0);
    Ciniii(a,b,k);
    int count = 0;
    for(int i= 10000;i>=1;i--){
        if(i==0) continue;
        if(a%i==0 && b%i==0) count++;
        if(count==k){
            cout << i << nn;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define int long long
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)


#define MOD 1000000007

long long mod_pow(long long a,long long b)
{
    a %= MOD;
    long long res = 1;
    while(b){
        if(b & 1){
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

#define MAX_N 200005
int inv[MAX_N],fac[MAX_N],finv[MAX_N];

void make()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for(int i=2;i<MAX_N;i++){
		inv[i] = MOD - (long long)inv[MOD%i] * (MOD/i) % MOD;
		fac[i] = (long long)fac[i-1] * i % MOD;
		finv[i] = (long long)finv[i-1] * inv[i] % MOD;
	}
}

int comb(int a,int b)
{
	if(a < b){
		return 0;
	}
	return fac[a] * ((long long)finv[b] * finv[a-b] % MOD) % MOD;
}
signed main(){
    make();
    int n,a,b,c;
    cin >> n >> a >> b >> c;
    if(a==0){
        int X = (b+c) * mod_pow(b,mod-2)%mod;
        cout << n*X%mod << endl;
    }else if(b==0){
        int X = (a+c) * mod_pow(a,mod-2)%mod;
        cout << n*X%mod << endl;
    }else{
        int X,Y;
        int p,q;
        X = (100LL) * mod_pow(100LL-c,mod-2)%mod;
        Y = (100LL) * mod_pow(100LL-c,mod-2)%mod;
        p = a * mod_pow(a+b,mod-2)%mod;
        q = b * mod_pow(a+b,mod-2)%mod;
        int dp[100010]={};
        int dp2[100010]={};
        int res = 0;
        for(int i=0;i<n;i++){
            dp[i] = comb(n-1+i,i)*mod_pow(p,n)%mod;
            dp[i] = dp[i]*mod_pow(q,i)%mod;
            res += dp[i] * ((X*n+Y*(i))%mod)%mod;
            res %= mod;
            dp2[i] = comb(n-1+i,i)*mod_pow(q,n)%mod;
            dp2[i] = dp2[i]*mod_pow(p,i)%mod;
            res += dp2[i] * ((Y*n+X*(i))%mod)%mod;
            res %= mod;
        }
        cout << res << endl;

    }
    return 0;
}

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

#define ll long long
#define P pair<int, int>
#define F first
#define S second

const ll mod = 1000000007LL;

ll n, a[100005], b[100005], c[100005], dp[100005][3];

void solve() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i] >> c[i];
  }

  dp[0][0] = a[0], dp[0][1] = b[0], dp[0][2] = c[0];
  for (int i = 1; i < n; i++) {
    dp[i][0] = a[i] + max(dp[i - 1][1], dp[i - 1][2]);
    dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][2]);
    dp[i][2] = c[i] + max(dp[i - 1][0], dp[i - 1][1]);
  }

  cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});
}

int main(int argc, char const *argv[]) {
/*#ifndef ONLINE_JUDGE
  freopen("practice/input.txt", "r", stdin);
  freopen("practice/output.txt", "w", stdout);
#endif*/

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

  int T = 1;
  while (T--) {
    solve();
  }

  return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define INF 0x7fffffff
using namespace std;
string s,t;
vector<ll>mp[26];
ll dp[3002][3002];
bool ans[3002];

ll solve(ll i,ll j){
    if(i == s.size() || j == t.size())
        return 0;
    if(dp[i][j] != -1)
        return dp[i][j];
    if(s[i] == t[j]){
        return dp[i][j] = 1 + solve(i+1,j+1);
    }
    return dp[i][j] = max(solve(i+1,j),solve(i,j+1));

}
void print(ll i,ll j){

    if(i == s.size() || j == t.size())
        return;
    if(s[i] == t[j]){
        ans[i] = true;
        print(i+1,j+1);
        return;
    }
    if(dp[i+1][j] < dp[i][j]){
        print(i,j+1);
    }else{
        print(i+1,j);
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    memset(dp,-1,sizeof dp);
    cin>>s>>t;
    solve(0,0);
    print(0,0);
    for(ll i = 0; i < 3002; i++){
        if(ans[i])
            cout<<s[i];
    }
    return 0;
}




//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
//ios::sync_with_stdio(0);cin.tie(0);


Measured memory_bytes: 70912
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MAXN = 1e5+200;
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    int p = (a + b + c) / 2;
    cout<<sqrt(p*(p-a)*(p-b)*(p-c))<<endl;
    return 0;
}


Measured memory_bytes: 256