akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <list>
#include <tuple>
#include <bitset>
#include <ciso646>

using namespace std;

inline bool cheak(int x, int y, int xMax, int yMax){ return x >= 0 && y >= 0 && xMax > x && yMax > y; }
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
template<class T> inline T sqr(T x) { return x*x; }

typedef pair<int, int> P;
typedef tuple<int, int, int> T;
typedef long long ll;
typedef unsigned long long ull;

#define For(i,a,b)	for(int (i) = (a);i < (b);(i)++)
#define rep(i,n)	For(i,0,n)
#define Fill(a,v)	fill((int*)a,(int*)(a+(sz(a)/sz(*(a)))),v)
#define clr(a)		memset((a), 0 ,sizeof(a))
#define mclr(a)		memset((a), -1 ,sizeof(a))
#define all(a)		(a).begin(),(a).end()
#define sz(a)		(sizeof(a))

const int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 }, dy[8] = { 0, 1, 0, -1, -1, 1, -1, 1 };
const int mod = 1000000007;
const int INF = 1e9;

int main()
{
	int w, h;

	while (cin >> w >> h && w){
		int b[50][50];
		int d[50][50][4];
		Fill(d, INF);

		rep(y, h)rep(x, w){
			cin >> b[y][x];
		}
		int c[4];
		cin >> c[0] >> c[1] >> c[2] >> c[3];

		d[0][0][0] = 0;
		queue<T> q;
		q.push(T(0, 0, 0));
		while (q.size()){
			int y = get<0>(q.front()), x = get<1>(q.front()), dir = get<2>(q.front());
			q.pop();
			rep(i, 4){
				int cost = c[i];
				if (b[y][x] == i)cost = 0;
				int nd = (dir + i) % 4;
				int ty = y + dy[nd], tx = x + dx[nd];
				if (cheak(tx, ty, w, h) and d[ty][tx][nd] > d[y][x][dir] + cost){
					d[ty][tx][nd] = d[y][x][dir] + cost;
					q.push(T(ty, tx, nd));
				}
			}
		}
		int ans = INF;
		rep(i, 4){
			ans = min(ans,d[h - 1][w - 1][i]);
		}

		cout << ans << endl;

	}
	return 0;
}

Measured memory_bytes: 1284
import sys
input = sys.stdin.readline
from itertools import *
from collections import *

INF = float('inf')


def main():
    A, B = map(int, input().split())
    yohaku = A - 2 * B
    print(yohaku if yohaku > 0 else 0)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,r,c,tot,val[500010],e[500010],nt[500010],hd[500010],v[500010],mp[500010],a[500010],tx,ty;
void build(ll x,ll y,ll w){
	tot++;
	e[tot]=y;val[tot]=w;
	nt[tot]=hd[x];hd[x]=tot;
}
ll dfs(ll x){
	ll i;
	v[x]=1;
	for(i=hd[x];i;i=nt[i]){
		if(!v[e[i]]){
			a[e[i]]=val[i]-a[x];
			if(!dfs(e[i]))return 0;
		}
		 else if(a[e[i]]+a[x]!=val[i])return 0;
	}
	return 1;
}
ll find(ll x){
	ll i;
	mp[x]=1;
	if(x<=r)tx=min(tx,a[x]);
	 else ty=min(ty,a[x]);
	for(i=hd[x];i;i=nt[i])if(!mp[e[i]])find(e[i]);
}
int main(){
	ll i,x,y,w;
	scanf("%lld%lld%lld",&r,&c,&n);
	for(i=1;i<=n;i++){
		scanf("%lld%lld%lld",&x,&y,&w);
		build(x,r+y,w);build(r+y,x,w);
	}
	for(i=1;i<=r+c;i++)if(!v[i]){
		if(!dfs(i))return puts("No"),0;
		tx=1e18;ty=1e18;
		find(i);
		//printf("%lld %lld\n",tx,ty);
		if(tx+ty<0)return puts("No"),0;
	}
	puts("Yes");
}
/*
极其巧妙的问题，可惜我不会（
*/

Measured memory_bytes: 29568
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
 
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<stdarg.h>
#include<malloc.h>

int main()
{
	int i, j, n, a[5000], sum=-100000, buf=0;
	
	while(1){
		scanf("%d", &n);
		if(n==0)
			break;
		for(i=0; i<n; i++)
			scanf("%d", &a[i]);

		for(i=0; i<n; i++){
			for(j=i; j<n; j++){
				buf += a[j];
				if(sum < buf)
					sum = buf;
			}
			buf = 0;
		}
		printf("%d\n", sum);
		sum=-100000;
	}
	return 0;
}

Measured memory_bytes: 616
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;
 
int gcd(int x,int y){
    if(y==0)return x;

    return gcd(y,x%y);
}
int lcm(int x,int y){
    return x*y/gcd(x,y);
}

int main(){

    int A,B;
    cin>>A>>B;

    if(B%A==0){
        cout<<A+B<<endl;
    }else{
        cout<<B-A<<endl;
    }

    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
H = [0] + list(map(int, input().split()))
s = set()

for _ in range(M):
    A, B = map(int, input().split())
    if H[A] >= H[B]:
        s.add(B)
    if H[A] <= H[B]:
        s.add(A)

print(N - len(s))

Measured memory_bytes: 20092
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long a = sc.nextLong();
    long b = sc.nextLong();

    System.out.println(lcm(a,b));

  }

  public static long lcm (long a, long b) {
    return a * b / gcd(a,b);
  }

  public static long gcd (long a, long b) {
    if (a < b) return gcd(b,a);
    if (b == 0) return a;
    return gcd(b,a%b);
  }
}


Measured memory_bytes: 23764
//It doesn't matter how slow you go, Unless you don't stop.
#include<iostream>
#include<algorithm>
#include<bitset>
 
#include<cmath>
#include<cstring>
#include<climits>
 
#include<deque>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
 
#include<fstream>
#include<chrono>
using namespace std;
 
typedef long long LL;
typedef pair<LL,LL> p64;
typedef vector<LL> v64;
typedef map<LL,LL> mp64;
 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i,s,e) for(long long i=s;i<=e;i++)
#define brep(i,s,e) for(long long i=s;i>=e;i--)
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define DANGER std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
LL knapsack(LL W[],LL v[],int wght,int n)
{
    LL ** dp = new LL * [n+1];
    for(int i=0;i<=n;i++)
    {
        dp[i] = new LL [wght+1];
        for(int j=0;j<=wght;j++)
        {
            dp[i][j] = 0;
        }
    }
    for(int i=0;i<=wght;i++)
    {
        dp[0][i] = 0;
    }
    for(int i=0;i<n;i++)
    {
        dp[i][0] = 0;
    }
    //solve
    for(int i=1;i<=n;i++)
    {
        for(int w=0;w<=wght;w++)
        {
            dp[i][w] = dp[i-1][w];
            if(W[i-1]<=w)
            {
                //cout<<W[i-1]<<" "<<w<<endl;
                dp[i][w] = max(dp[i][w],dp[i-1][w-W[i-1]]+v[i-1]);
            }
        }
    }
    // for(int i=0;i<=n;i++)
    // {
    //     for(int j=0;j<=wght;j++)
    //     {
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<endl;
    // }
    // cout<<endl;
    return dp[n][wght];
} 
void solve()
{
     int n,wght;
     cin>>n>>wght;
     LL w[n],v[n];
     for(int i=0;i<n;i++)
     {
        LL x,y;cin>>x>>y;
         w[i] = x;
         v[i] = y;
     }
     LL ans = knapsack(w,v,wght,n);
     cout<<ans<<endl;
}
 
int main()
{
    DANGER;
    ofstream out("output.txt");
 
    auto start = chrono::high_resolution_clock::now();
    
    LL t = 1;
    // cin>>t;
    rep(test,1,t)
    {
        solve();
    }
    
    auto stop = chrono::high_resolution_clock::now();
    // auto duration = chrono::duration_cast<chrono::milliseconds>(stop - start); 
    // cout << "Time taken by function: " << duration.count() << " milliseconds" << endl;
}

Measured memory_bytes: 79488
from functools import reduce
  
def comb(n, k, p):
  """power_funcを用いて(nCk) mod p を求める"""
  a = reduce(lambda x,y: x*y%p, range(n,n-k,-1))
  b = reduce(lambda x,y: x*y%p, range(1,k+1))
  return (a*pow(b, p-2, p))%p
  
n, a, b = map(int, input().split())

MOD = 10**9 + 7


print((pow(2,n,MOD) - 1 - comb(n, a, MOD) - comb(n, b, MOD))%MOD)

Measured memory_bytes: 4068
S = sorted(set(input()))
alp = 'abcdefghijklmnopqrstuvwxyz'
if len(S) == len(alp):
    print(None)
    exit()
for i in range(len(S)):
    if S[i] != alp[i]:
        print(alp[i])
        exit()
print(alp[len(S)])


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
//T+N
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll k, a, b;
    cin >> k >> a >> b;
    for(ll ind = a; ind <= b; ind ++) {
        if(ind % k == 0) {
            cout << "OK";
            return 0;
        }
    }
    cout << "NG";

    return 0;
}



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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<int>v(n); for(auto&i:v)cin>>i;
	int cnt=0;
	for(int i=0;i<n-1;++i){
		int mn=i;
		for(int j=i+1;j<n;++j){
			if(v.at(j)<v.at(mn))mn=j;
		}
		if(i!=mn){
			int tmp=v.at(i);
			v.at(i)=v.at(mn);
			v.at(mn)=tmp;
			++cnt;
		}
	}
	for(int i=0;i<n;++i){
		cout<<v.at(i);
		if(i!=n-1)cout<<" "s;
		else cout<<"\n"s<<cnt<<"\n"s;
	}
}


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

int main(){
    string str;
    int number = 0;
    int sum = 0;
    while(getline(cin, str)){
        for(int i=0; i<=str.size(); ++i){
            if('0' <= str[i] && str[i] <= '9'){
                number *= 10;
                number += str[i] - '0';
            }else{
                sum += number;
                number = 0;
            }
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 0
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author silviase
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AABCSwap solver = new AABCSwap();
        solver.solve(1, in, out);
        out.close();
    }

    static class AABCSwap {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int x = in.nextInt();
            int y = in.nextInt();
            int z = in.nextInt();
            out.println(z + " " + x + " " + y);
        }

    }
}



Measured memory_bytes: 22228
P, Q, R = map(int, input().split())
a1 = min(P, Q, R)
if a1 == P:
    a2 = min(Q, R)
if a1 == Q:
    a2 = min(P, R)
if a1 == R:
    a2 = min(P, Q)

print(a1 + a2)

Measured memory_bytes: 3060
/*
 
श्रीगुरु चरन सरोज रज
निजमनु मुकुरु सुधारि
बरनउँ रघुबर बिमल जसु
जो दायकु फल चारि
बुद्धिहीन तनु जानिके, सुमिरौं पवन-कुमार
बल बुधि बिद्या देहु मोहिं, हरहु कलेस बिकार 
 
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD (ll)1000000007

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int a, b;
    cin >> a >> b;
    if (b == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    ll count = 1;
    while (count * a - count + 1 < b)
    {
        count++;
    }
    cout << count;
}

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


n, c = map(int, input().split())
tv_guide = []
for _ in range(n):
    start, end, channel = map(int, input().split())
    tv_guide.append([start, 1, channel-1])
    tv_guide.append([end, 0, channel-1])

tv_guide.sort(key=lambda x:(x[0], -x[1]))

channel_count = [0] * c
channel_set = set()
ans = 0
for time, on, channel in tv_guide:
    if on:
        channel_set.add(channel)
        channel_count[channel] += 1

    else:
        channel_count[channel] -= 1
        if channel_count[channel] == 0:
            channel_set.discard(channel)

    candidate = len(channel_set)
    if ans < candidate:
        ans = candidate

print(ans)

Measured memory_bytes: 46072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
int n,s;
int a[3005];
ll mem[3005][3005];
ll ans = 0;
ll dp(int id, int W){
    if (id == 0) return (W == 0);
    if (mem[id][W] != -1) return mem[id][W];
    ll res = 2*dp(id-1,W);
    if (W >= a[id]) {
        res += dp(id-1,W-a[id]);
    }
    res %= mod;
    return mem[id][W] = res;
}
int main(){
    scanf("%d%d",&n,&s);
    for (int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    memset(mem,-1,sizeof(mem));
    printf("%lld", dp(n,s));

}


Measured memory_bytes: 74516
def f(s,t,k):
 n=len(s)
 if k>n: return 0
 a=max(t,int(s[0]))
 z=0
 if a==0:z=f(s[1:],t,k)
 elif k==1:z=a+(n-1)*9
 else:
  if k-1<=n:z+=f(s[1:],9,k)
  z+=(a-1)*f(s[1:],9,k-1)
  z+=f(s[1:],t,k-1)
 return z
print(f(input(),0,int(input())))


Measured memory_bytes: 41192
#include<stdio.h>
#define N 100
int n,M[N][N];
int color[N],d[N],f[N],start;
void dfs_visit(int u){
	color[u] = 1;
	d[u] = ++start;
	for(int i=0;i<n;i++){
		if(!M[u][i]) continue;
		if(!color[i])
			dfs_visit(i);
	}
	f[u] = ++start;
}
void dfs(){
	start = 0;
    for(int i=0;i<n;i++)
            if(!color[i])
	            dfs_visit(i);
	for(int i=0;i<n;i++)
		printf("%d %d %d\n",i+1,d[i],f[i]);
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int u,k,v;
		scanf("%d%d",&u,&k);
		while(k--){
			scanf("%d",&v);
			M[u-1][v-1] = 1;
		}
	}
	dfs();
	return 0;
}


Measured memory_bytes: 2100
import sys
#import math


# input = sys.stdin.readline

def binary_search(arr, key,j):
    ok = j
    ng = len(arr)

    while abs(ok - ng) > 1:
        mid = int((ok + ng) / 2)

        if arr[mid] < key:
            ok = mid
        else:
            ng = mid

    return ok


def main():
    N = int(input())
    L = sorted(list(map(int, input().split())))
    ans =0
    for i in range(N-2):
        for j in range(i+1,N-1):
            ok = binary_search(L,L[i]+L[j],j)
            ans += ok-j
    print(ans)
if __name__ == "__main__":
    main()


Measured memory_bytes: 74068
#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

int main(){
	ll Q, H, S, D, n;
	scanf("%lld %lld %lld %lld", &Q, &H, &S, &D);
	H = min(Q * 2, H);
	S = min(H * 2, S);
	D = min(S * 2, D);
	
	scanf("%lld", &n);
	ll res = (n / 2) * D + (n % 2) * S;
	printf("%lld\n", res);
}

Measured memory_bytes: 128
h,w = map(int, input().split())
s = [list(input()) for _ in range(h)]
black = []
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            black.append([i,j])
for x,y in black:
    flag = False
    for a,b in [(0,1), (1,0), (0,-1), (-1,0)]:
        if [x+a, y+b] in black: flag = True
    if not flag:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 9248
import sys
input = sys.stdin.readline
def print_ans(N):
    """Test Case
    >>> print_ans(11)
    9
    >>> print_ans(136)
    46
    >>> print_ans(100000)
    90909
    """
    counter = 0
    for i in range(1, N + 1):
        if len(str(i)) % 2 != 0:
            counter +=1
    print(counter)

if __name__ == '__main__':
    N = int(input().rstrip())
    print_ans(N)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std ;
#define ll long long int
#define pb push_back
#define fi first 
#define se second 
#define mod 1000000007
/* Iterative Function to calculate (x^y) in O(log y) */
ll power(ll x, ll y) 
{ 
	int res = 1;	 // Initialize result 

	while (y > 0) 
	{ 
		// If y is odd, multiply x with result 
		if (y & 1) 
			res = res*x; 

		// y must be even now 
		y = y>>1; // y = y/2 
		x = x*x; // Change x to x^2 
	} 
	return res; 
}

int power(ll x, ll  y, ll p)  
{  
    ll res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}  
int main() 
{ 
  ll n ;
  cin >> n ;
  vector<string> v(n) ;
  for(ll i=0;i<n;i++)
  {
    ll a ;
    cin >> a ;
    ll j =50 ;
    while(j--)
    {
      if(a%2==0) v[i] += '0' ;
      else v[i] += '1' ;
      a = a/2 ;
    }
  }
  // for(ll i=0;i<n;i++)
  // cout << v[i] << endl;
  string s;
  for(ll i=0;i<=50;i++)
  {
    ll cnt=0;
    for(ll j=0;j<n;j++)
    {
      if(v[j][i]=='1') cnt++ ;
    }
    if(cnt%2==0) s += '0' ;
    else s += '1' ;
  }
  for(ll i=0;i<n;i++)
  {
    string s2 = "" ;
    for(ll j=0;j<s.size();j++)
    {
      if(v[i][j]==s[j]) s2 += '0' ;
      else s2 += '1' ;
    }
     ll a=0 ;
    for(ll j=0;j<s2.size();j++)
    {
     a += (s2[j]-'0')*(power(2,j)) ;
    }
    cout << a << " " ;

  }
  cout <<  endl;


} 

Measured memory_bytes: 25176
using System;
using System.Linq;
class abc124_b{
  static void Main(){
    var n=int.Parse(Console.ReadLine());
    var hs=Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    
    var result=1;
    var max=hs[0];
    
    for(int i=1;i<n;i++){
      if(max<=hs[i]){
        max=hs[i];
        result++;
      }
    }
    
    Console.WriteLine(result);
    return;
  }
}


Measured memory_bytes: 13268
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	n := iScan()
	m := iScan()
	x := iSScan(m)
	sort.Ints(x)
	y := make([]int, m-1)
	for i := 0; i < m-1; i++ {
		y[i] = x[i+1] - x[i]
	}
	sort.Ints(y)
	ans := 0
	if n < m {
		for i := 0; i < m-n; i++ {
			ans += y[i]
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 4152
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
using namespace std;

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

Measured memory_bytes: 4392
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, a[100005] = {}, b[100005] = {}, c[100005] = {};
    ll z = 0;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    a[n] = b[n] = c[n] = 1000000007;
    sort(a, a + n);
    sort(b, b + n);
    sort(c, c + n);
    for (int i = 0; i < n; i++) z += 1ll * (lower_bound(a, a + n + 1, b[i]) - a) * (n - (upper_bound(c, c + n + 1, b[i]) - c));
    cout << z;
}


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

#define mod 1000000007
#define ten5 100005
#define ten52 200005
#define ten6 1000005
#define PI 3.1415926

typedef long long int ll;

//ll num[ten52];
//ll num[10][10];
set<ll> sll;

int main(void)
{
    long long int sum=0,range=0,ceiling;
    double ans=0.0,half;
    long long int m,n,o,i,j,k=0,money;
    long long int a,a1=0,a2=0,a3=0,ar,as,at1;
    char c;
    a=a1=a2=a3=0;
    //vector <int> v;
    //float f,g,h;
    //int c,d,big=0;
    string s,s1,s2;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a;
        if(sll.find(a)==sll.end()) sll.insert(a);
        else
        {
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
    return 0;
}





Measured memory_bytes: 9600
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

/* --------------------------------------------------- */

int main() {
    ll n, m;
    cin >> n >> m;
    ll ans = 0;
    ll x = min(n, m / 2);
    ans += x;
    m -= 2 * x;
    ans += m / 4;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
A = LI()
wa = 0
for i in range(N):
    wa += 1/A[i]
print(1/wa)

Measured memory_bytes: 68652
def main():
    N, M = map(int, input().split())
    ans = editorial(N, M)
    print(ans)


def editorial(N, M):
    """
    1 回の実行にかかる時間を x ms
    全てのケースに正解する確率を p
    この問題の答えを y ms

    x = 1900M + 100(N − M)
    p = (1/2)^M

    まず，一回目の提出で必ず x ms はかかる
    その後は，確率 p で終了
    そして確率 1 − p でその提出には失敗し，更に提出を繰り返す
    確率 1 − p で失敗した場合の，その時点からかかる時間の期待値は y ms
    よって，y = x + (1 − p) × y が成立し
    これを解くと y = x/p が得られる
    答えは x/p = (1900M + 100(N − M)) × 2M
    """
    return (1900 * M + 100 * (N - M)) * (2 ** M)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
from decimal import *
N,K = map(int, raw_input().split())
ans = Decimal(0)
if N >= K:
	ans += Decimal(N-K+1)/Decimal(N)
pre = min(N+1,K)
sisu = 1
while True:
	if(pre == 1):
		break
	now = K - (K * (2**sisu - 1))/ (2**sisu)
	if(pre > now):
		ans += Decimal(pre-now)/Decimal(N * 2**sisu)
	sisu += 1
	pre = min(now,N+1)
print(ans)

Measured memory_bytes: 4268
#include <stdio.h>
#include <string.h>

int main() {

    int arr[3][3];
    int a, n, b;

    for (int i = 0; i < 3; i++) {
        scanf("%d", &a);
        arr[0][i] = a;
    }
    for (int i = 0; i < 3; i++) {
        scanf("%d", &a);
        arr[1][i] = a;
    }
    for (int i = 0; i < 3; i++) {
        scanf("%d", &a);
        arr[2][i] = a;
    }
    scanf("%d", &n);
    for (int j = 0; j < n; j++) {
        scanf("%d", &b);
        for (int k = 0; k < 3; k++) {
            for (int l = 0; l < 3; l++) {
                if (arr[k][l] == b) {
                    arr[k][l] = 0;
                    break;
                }
            }
        }
    }

    int isCheck = 0;

    //縦に揃う（３pt）
    if (arr[0][0] == 0 && arr[1][0] == 0 && arr[2][0] == 0) {
        isCheck = 1;
    } else if (arr[0][1] == 0 && arr[1][1] == 0 && arr[2][1] == 0) {
        isCheck = 1;
    } else if (arr[0][2] == 0 && arr[1][2] == 0 && arr[2][2] == 0) {
        isCheck = 1;
        //横に揃う（３pt）
    } else if (arr[0][0] == 0 && arr[0][1] == 0 && arr[0][2] == 0) {
        isCheck = 1;
    } else if (arr[1][0] == 0 && arr[1][1] == 0 && arr[1][2] == 0) {
        isCheck = 1;
    } else if (arr[2][0] == 0 && arr[2][1] == 0 && arr[2][2] == 0) {
        isCheck = 1;
        //斜めに揃う（2pt）
    } else if (arr[0][0] == 0 && arr[1][1] == 0 && arr[2][2] == 0) {
        isCheck = 1;
    } else if (arr[0][2] == 0 && arr[1][1] == 0 && arr[2][0] == 0) {
        isCheck = 1;
    }


    printf("%s", (isCheck == 1 ? "Yes" : "No"));


    return 0;
} 

Measured memory_bytes: 128
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int A, B; cin >> A >> B;
    cout << max(0, A-2*B) << endl;
	
	return 0;
}
 
// read the question correctly (ll vs int)
// template by bqi343



Measured memory_bytes: 256
# 解き直し
# 負数が偶数なら全部+にできる 奇数ならすべてを正数にして一番ちいさいやつを引く
n = int(input())
arr = list(map(int, input().split()))
minus_n = 0
positive_arr = list(sorted(list(map(lambda x: abs(x), arr))))
for a in arr:
    if a < 0:
        minus_n += 1

if minus_n % 2 == 0:
    print(sum(positive_arr))
else:
    print(sum(positive_arr) - positive_arr[0] * 2)



Measured memory_bytes: 14332
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<utility>
#include<numeric>
#include<vector>
#include<map>
#include<set>
#include<tuple>
#include<stack>
#include<queue>
#include<functional>
#include<iterator>
#include<cmath>
#include<cctype>

using namespace std;

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

const int INF = 1e9;
const ll LINF = 1e18;

struct edge{int to,cost;};


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

	int n;
	cin >> n;
	
	ll d[n];
	for(int i=0;i<n;i++) d[i] = LINF;

	int a,b,c;
	vector<edge> es[n];
	for(int i=0;i<n-1;i++){
		cin >> a >> b >> c;
		a--;b--;
		es[a].push_back(edge{b,c});
		es[b].push_back(edge{a,c});
	}
	int q,k;
	cin >> q >> k;
	k--;
	
	priority_queue<P,vector<P>,greater<P>> que;
	d[k] = 0;
	que.push(P(0,k));
	while(!que.empty()){
		P tmp = que.top(); que.pop();
		int t = tmp.second;
		ll cost = tmp.first;
		
		if(d[t] < cost) continue;
		for(int i=0;i<es[t].size();i++){
			edge e = es[t][i];
			if(d[e.to] > d[t] + e.cost){
				d[e.to] = d[t] + e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
	int x,y;
	for(int i=0;i<q;i++){
		cin >> x >> y;
		cout << d[--x]+d[--y] << "\n";
	}

	return 0;
}

Measured memory_bytes: 10096
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def div_mod(a, b, mod):
    return a * pow(b, mod - 2, mod) % mod


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
#
# N = 5
# AB = generate_tree(N, directed=False)
# AB = [(a + 1, b + 1) for a, b in AB]
# print(N)
# for a, b in AB:
#     print(a, b)
# plot_graph(AB)


# 解説
# 辺に着目すれば絶対2つに木を分割できるので計算が簡単になる

graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# S の頂点数の期待値 - 黒の数の期待値
# 両側の部分木に黒がある場合、その辺は S に含まれる
root = 0
stack = [(0, None)]
hist = []
while stack:
    v, parent = stack.pop()
    hist.append((v, parent))
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))

subtree_sizes = [0] * N
hist.reverse()
for v, parent in hist:
    ret = 0
    for u in graph[v]:
        if u == parent:
            continue
        ret += subtree_sizes[u]
    subtree_sizes[v] = ret + 1

pow2 = [1]
p = 1
for _ in range(N + 10):
    p = p * 2 % MOD
    pow2.append(p)

# 辺の数の期待値 * 2**N
# すべてのパターンに含まれる辺の数の合計
e_exp = 0
for v in range(N):
    for u in graph[v]:
        if v < u:
            continue
        # 両側の頂点数
        s = min(subtree_sizes[v], subtree_sizes[u])
        t = N - s

        # 全部のパターン数から全部白のパターン数を引く
        cnt = pow2[N]
        # s が全部白のぱたーん数
        cnt -= pow2[t]
        # t が全部白のぱたーん数
        cnt -= pow2[s]
        # 引きすぎ
        cnt += 1
        e_exp += cnt
        e_exp %= MOD
# 頂点数は辺の数 + 1
# 全部白の場合空グラフになるので1つ減らす
v_exp = e_exp + pow2[N] - 1
ans = div_mod(v_exp, pow2[N], MOD) - div_mod(N, 2, MOD)
ans %= MOD
print(ans)
# print((v_exp / (2 ** N)) - N / 2)


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

#define fa(x,v) for(auto x:v)
#define f(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define spc " "
#define endl '\n'
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define len(s) (ll)int(s.length())
#define sz(v) (ll)int(v.size())
#define MOD 1000000007

void Fast_IO() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    #ifdef rsd511
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    #endif
    #ifndef rsd511
    #define trace(...) {}
    #define cotra(...) {}
    #endif
} 

// Code Here

ll n, m;
vector < vector <ll> > adj;
vector <ll> vis;
ll CC;

void dfs(ll u)
{
	vis[u] = 1; CC++;
	fa(v,adj[u]) if(!vis[v]) dfs(v);
}

int main()
{
    Fast_IO();
    cin >> n >> m;
    adj.resize(n);
    vis.assign(n,0);
    f(_,1,m) {
    	ll u, v; cin >> u >> v;
    	u--; v--;
    	adj[u].pb(v);
    	adj[v].pb(u);
    }	
    ll ans = 0;
    f(i,0,n-1) if(!vis[i]) {
    	CC = 0;
    	dfs(i);
    	ans = max(ans, CC);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 21860
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x[] = new int[n];

		for (int i = 0; i < n; i++) x[i] = sc.nextInt();

		int ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					if (x[i] != x[j] && x[j] != x[k] && x[i] != x[k] && x[i] + x[j] > x[k] && x[i] + x[k] > x[j] && x[j] + x[k] > x[i]) ans++;
				}
			}
		}

		System.out.println(ans);



		sc.close();

	}

}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
    ll n;cin >>n;
    vector<ll>a(n);
    for (int i = 0; i < n; ++i) {
        cin >>a[i];
    }
    ll ans=0;
    sort(all(a));
    reverse(all(a));
    ans=a[0];
    int cnt=2;
    if(n!=2) {
        for (int i = 1; i < n; ++i) {
            ans += a[i];
            cnt++;
            if (cnt == n)break;
            ans += a[i];
            cnt++;
            if (cnt == n)break;
        }
    }
    cout <<ans <<endl;
}


Measured memory_bytes: 4832
#include <bits/stdc++.h>
using namespace std;
#define int long long

typedef long long ll;
typedef unsigned long long ull;
//typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod


int n, m;
vector<vector<int>> g(1000000 + 6);

int ord[1000000 + 6], low[1000000 + 6];
bool visited[1000000 + 6];

vector<pair<int, int>> Bridges;
vector<int> Points;

void dfs(int now, int par, int &cnt) {
    visited[now] = true;
    ord[now] = cnt++;
    low[now] = ord[now];
    for (auto nx : g[now]) {
        if (!visited[nx]) {
            dfs(nx, now, cnt);
            low[now] = min(low[now], low[nx]);
        }
        else if (nx != par) {
            low[now] = min(low[now], ord[nx]);
        }
        //???????????????
        if (ord[now] < low[nx]) {
            Bridges.push_back({min(now, nx), max(now, nx)});
        }
    }
    //??¢??????????????????
    if (par == -1) {
        if (g[now].size() >= 2) Points.push_back(now);
    }
    else if (ord[par] <= low[now]) {
        Points.push_back(par);
    }
    return;
}

void lowlink (int n, vector<vector<int>>& g) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, -1, cnt);
        }
    }
    sort(all(Bridges));
    sort(all(Points));
    return;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    lowlink(n, g);
    rep(i, Bridges.size()) {
        cout << Bridges[i].fi << " " << Bridges[i].se << endl;
    }
}

Measured memory_bytes: 28644
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<int>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    int n,m;
    cin >> n >> m;
    matrix gra(n+1,vi(0));
    rp(i,m){
        int a,b;
        cin >> a >> b;
        gra[a].pb(b);
        gra[b].pb(a);
    }
    queue<P> que;
    vi seen(n+1,0);
    vi ans(n+1,0);
    que.push(mp(1,0));
    while(!que.empty()){
        P p=que.front(); que.pop();
        ans[p.first]=p.second;
        for(auto nxt:gra[p.first]){
            if(seen[nxt]==0){
            que.push(mp(nxt,p.first));
            seen[nxt]=1;
            }
        }
    }
    repi(i,2,n+1){
        if(ans[i]==0){
            print("No");
            return 0;
        }
    }
    print("Yes");
    repi(i,2,n+1){
        print(ans[i]);
    }
    return 0;
}

Measured memory_bytes: 10792
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;
const double EPS = 1e-6;

int n;
double dp[301][301][301];

double calc(int x, int y, int z){
    if(dp[x][y][z] > -EPS) return dp[x][y][z];
    double res = 0.0;
    double num = 1.0 * n / (n - z);
    if(x != n) res += (calc(x + 1, y, z) + num) * 1.0 * (n - x) / (n - z);
    if(y != x) res += (calc(x, y + 1, z) + num) * 1.0 * (x - y) / (n - z);
    if(z != y) res += (calc(x, y, z + 1) + num) * 1.0 * (y - z) / (n - z);
    return dp[x][y][z] = res;
}

signed main(){
    cin >> n;
    int x = n, y = n, z = n;
    rep(i, 0, n){
        int a;
        cin >> a;
        if(a == 1){
            z--;
        }else if(a == 2){
            z--; y--;
        }else if(a == 3){
            z--; y--; x--;
        }
    }
    rep(i, 0, n + 1) rep(j, 0, n + 1) rep(k, 0, n + 1) dp[i][j][k] = -1.0;
    dp[n][n][n] = 0.0;
    printf("%.15f\n", calc(x, y, z));
}

Measured memory_bytes: 213376
#include <stdio.h>

int a, b, c;
int main(void){
    scanf("%d %d %d", &a, &b, &c);
    if(a>b&&a>c){
        printf("A\n");
    }else if (b>c){
        printf("B\n");
    }else{
        printf("C\n");
    }
    return 0;
}



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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm( a, b ) (a)/__gcd((a),(b))*(b)
#define endl '\n'

using namespace std;

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

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

LL fac[SIZE], finv[SIZE], inv[SIZE];
void combInit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for( int i = 2; i < SIZE; ++i ) {
        fac[i] = (fac[i - 1] * i) % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = (finv[i - 1] * inv[i]) % MOD;

    }
}

LL comb(int n, int k) {
    if( n < k ) return 0;
    if( n < 0 || k < 0 ) return 0;
    return (fac[n] * (finv[k] * finv[n - k] % MOD)) % MOD;

}

vector< int > Div( int n ) {
    vector< int > ret;
    for( int i = 1; i * i <= n; ++i ) {
        if( n % i == 0 ) {
            ret.pb( i );

            if( i * i != n ) ret.pb( n / i );
        }
    }
    sort( all( ret ) );
    return ret;
}

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

    int w, h;
    cin >> w >> h;
    int n;
    cin >> n;
    int mp[105][105] = {};

    while( n-- ) {
        int x, y, a;
        cin >> x >> y >> a;
        if( a == 1 ) {
            for( int i = 1; i <= h; ++i ) {
                for( int j = 1; j <= x; ++j ) {
                    mp[i][j] = 1;

                }
            }
        } else if( a == 2 ) {
            for( int i = 1; i <= h; ++i ) {
                for( int j = x + 1; j <= w; ++j ) {
                    mp[i][j] = 1;

                }
            }
        } else if( a == 3 ) {
            for( int i = 1; i <= y; ++i ) {
                for( int j = 1; j <= w; ++j ) {
                    mp[i][j] = 1;

                }
            }
        } else if( a == 4 ) {
            for( int i = y + 1; i <= h; ++i ) {
                for( int j = 1; j <= w; ++j ) {
                    mp[i][j] = 1;

                }
            }
        }
    }
    
    int c = 0;
    for( int i = 0; i <= h; ++i ) {
        for( int j = 0; j <= w; ++j ) {
            c += mp[i][j];

        }
    }
    cout << (w * h) - c << endl;
    return 0;
}



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

using namespace std;

int dfs(int in, vector<int> adj[], int dp[]) {
	if(dp[in]>0) return dp[in];
	dp[in] = 1;
	for(auto node: adj[in]) {
		dp[in] = max(dp[in], 1+dfs(node, adj, dp));
	}
	return dp[in];
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<int> adj[n];
	while(m--) {
		int x, y;
		scanf("%d%d", &x, &y);
		x--;
		y--;
		adj[x].push_back(y);
	}
	int dp[n];
	memset(dp, 0, sizeof dp);
	int ans = 0;
	for(int i=0; i<n; i++) {
		if(dp[i]==0) {
			ans = max(ans, dfs(i, adj, dp));
		}
	}
	printf("%d\n", ans-1);
    return 0;
}

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


int MinSteps(int arr[],int N)
{
  int dp[N];
  
  dp[N-1] = 0,dp[N-2] = abs(arr[N-1]-arr[N-2]);
  
  for (int i = N-3; i>=0;i--)
  {
   dp[i] = min(dp[i+1]+abs(arr[i]-arr[i+1]),dp[i+2]+abs(arr[i]-arr[i+2]));
  }
  return dp[0];
}
int main()
{
  int N;
  cin >> N;
  int arr[N];
  for (int i = 0;i<N;i++)
  cin >> arr[i];
  
  cout << MinSteps(arr,N) << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);


static int cntdiv[210];

void cntdivisors(int n){
 //int div[n];
  cntdiv[0] = 0;
  for(int i = 1; i <= n; i++ ){
    cntdiv[i] = 1;
  }

  for(int i = 2; i <= n; ++i){
    int j = i;
    while(j <= n){
      ++cntdiv[j];
      j = j + i;
    }
  }
}

int main(){
  int n;
  cin >> n;

  cntdivisors(201);
  int cnt = 0;


  REP(i,n+1){
    if (i % 2 != 0 && cntdiv[i] == 8) ++cnt;
  }
  cout << cnt << endl;

  return 0;
}


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

int main() {
  int n, a, x ;
  cin >> n;
  cin >> a;
  
  if (a < 500) {
    x = n % 500;
    if (x <= a || x==0) {
        cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
  else {
    cout << "Yes" << endl;
  }   
}

Measured memory_bytes: 256
a = list(input())
 
sign = "+-"
 
for i in range(2):  #1つめの正負
 for j in range(2):  #2つ目の正負
  for k in range(2):  #3つ目の正負
    if eval(a[0]+sign[i]+a[1]+sign[j]+a[2]+sign[k]+a[3] ) == 7:
     print(str(a[0]+sign[i]+a[1]+sign[j]+a[2]+sign[k]+a[3])+'=7')
     exit()


Measured memory_bytes: 9068
n, a, b, c = map(int, input().split())
ans = []
prev = ''
for _ in range(n):
    s = input()
    if 'C' not in s:
        if a == b == 0 and ans:
            # キングクリムゾン発動！
            prev_x = ans.pop()
            if prev_x == prev[0]:
                prev_y = prev[1]
            else:
                prev_y = prev[0]
            ans.append(prev_y)
            if prev_x == 'A':
                a -= 2
            elif prev_x == 'B':
                b -= 2
            else:
                c -= 2
            if prev_y == 'A':
                a += 2
            elif prev_y == 'B':
                b += 2
            else:
                c += 2
        if a < b:
            a += 1
            b -= 1
            ans.append('A')
        else:
            a -= 1
            b += 1
            ans.append('B')

    elif 'B' not in s:
        if a == c == 0 and ans:
            # キングクリムゾン発動！
            prev_x = ans.pop()
            if prev_x == prev[0]:
                prev_y = prev[1]
            else:
                prev_y = prev[0]
            ans.append(prev_y)

            if prev_x == 'A':
                a -= 2
            elif prev_x == 'B':
                b -= 2
            else:
                c -= 2
            if prev_y == 'A':
                a += 2
            elif prev_y == 'B':
                b += 2
            else:
                c += 2
        if a < c:
            a += 1
            c -= 1
            ans.append('A')
        else:
            a -= 1
            c += 1
            ans.append('C')
    elif 'A' not in s:
        if b == c == 0 and ans:
            # キングクリムゾン発動！
            prev_x = ans.pop()
            if prev_x == prev[0]:
                prev_y = prev[1]
            else:
                prev_y = prev[0]
            ans.append(prev_y)
            if prev_x == 'A':
                a -= 2
            elif prev_x == 'B':
                b -= 2
            else:
                c -= 2
            if prev_y == 'A':
                a += 2
            elif prev_y == 'B':
                b += 2
            else:
                c += 2
        if b < c:
            b += 1
            c -= 1
            ans.append('B')
        else:
            b -= 1
            c += 1
            ans.append('C')
    prev = s
    if -1 in (a, b, c):
        print('No')
        break
else:
    print('Yes')
    for x in ans:
        print(x)


Measured memory_bytes: 9948
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
k = int((2*N)**0.5)
if k*(k+1) == 2*N:
	print("Yes")
	print(k+1)
	ans = [[] for _ in range(k+1)]
	for i, (x, y) in enumerate(combinations(range(k+1), 2), 1):
		ans[x].append(i)
		ans[y].append(i)
	for l in ans:
		print(k, *l)

else:
	print("No")


Measured memory_bytes: 15856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;
//ll GCD(ll x,ll y){
//    if(y == 0) return x;
//    else return GCD(y,x%y);
//}

ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

ll LCM(ll a,ll b){
    return a / GCD(a,b) * b;
}

const int MOD = 1000000007;



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


Measured memory_bytes: 256
#
import sys
import math
import numpy as np
import itertools


# ひとつ入力
k = int(input())

a=[1,2,3,4,5,6,7,8,9]

if k < 10:
    print(k)
    exit()

for i in range(20):
    k -= len(a)
    b = []
    for j in a:
        r = j % 10 
        if r == 0:
            b.append(j*10)
            b.append(j*10+1)
        elif r == 9:
            b.append(j*10+8)
            b.append(j*10+9)
        else:
            b.append(j*10+r-1)
            b.append(j*10+r)
            b.append(j*10+r+1)
#    print(b,len(b),k)
    if k <= len(b):
        print(b[k-1])
        exit()
    a = b


Measured memory_bytes: 20120
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0,v[100005];
vector<int> g[100005];
void dfs(int x){
	if(v[x])return ;
	v[x]=1;
	for(int y:g[x])dfs(y);
}
int main() {
	cin>>n>>m;
	for(int i=1,x,y;i<=m;i++)cin>>x>>y,g[x].push_back(y),g[y].push_back(x);
	for(int i=1;i<=n;i++)if(!v[i])dfs(i),ans++;
	cout<<ans-1;
	return 0;
}

Measured memory_bytes: 9968