akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)

bool nibu(const vector<vector<int>> &G) {
    vector<int> color((int)G.size(), -1);
    color[0] = 0;
    function<bool(int)> dfs = [&](int cur) {
        for(auto &to : G[cur]) {
            if(color[to] != -1) {
                if(color[cur] == color[to]) return false;
            } else {
                color[to] = color[cur] ^ 1;
                if(!dfs(to)) return false;
            }
        }
        return true;
    };
    return dfs(0);
}

int solve() {
    int N; cin >> N;
    vector<vector<int>> G(N);
    rep(i, 0, N) rep(j, 0, N) {
        char a; cin >> a;
        if(a == '1') G[i].push_back(j);
    }
    if(!nibu(G)) return -1;
    int ans = 0;
    rep(s, 0, N) {
        queue<int> Q; Q.push(s);
        vector<int> dist(N, -1); dist[s] = 0;
        while(!Q.empty()) {
            int cur = Q.front(); Q.pop();
            for(auto &to : G[cur]) {
                if(dist[to] != -1) continue;
                Q.push(to);
                dist[to] = dist[cur] + 1;
                ans = max(ans, dist[to]);
            }
        }
    }
    return ans + 1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << solve() << '\n';
    return 0;
}


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

int main(){
  int N,K;
  cin>>N>>K;
  vector<int> a(N);
  int point1=0;
  for(int i=0;i<N;i++){
      cin>>a[i];
      if(a[i]==1){
          point1=i;
      }
  }
  
  cout<<(N-2)/(K-1)+1<<endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
	int n,x,m;
	cin>>n>>x>>m;
	vector<int>first(m,-1);
	vector<int>pre(2*m,0);
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(first[x]>=0){
			int loopsize = i-first[x];
			int loopsum = pre[i-1]-pre[first[x]-1];
			
			int loops = (n-i)/loopsize;
			
			ans += loops*loopsum;
			i+=loopsize*loops;
			for(int j=0;j<m;j++){
				first[j]=-1;
			}
		}
		if(i<pre.size()){
			pre[i]=pre[i-1]+x;
			first[x]=i;
		}
		
		ans += x;
		x = (x*x)%m;
	}
	
	cout<<ans<<endl;
}



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

pair<int,int> getScore() {
  int id;
  cin >> id;
  int a = 0, b = 0, ext = 0, s = 0, t = 0, sum = 0;
  for(int f = 1; f <= 10; ++f) {
    cin >> s;
    sum += s * (1 + a + b);
    b = a; a = 0;
    if(s == 10) {
      if(f == 10) ext = 2;
      else ++a;
      continue;
    }

    cin >> t;
    sum += t * (1 + a + b);
    b = a; a = 0;
    if(s+t == 10) {
      if(f == 10) ext = 1;
      else ++b;
      continue;
    }
  }
  while(ext--) {
    cin >> s;
    sum += s * (1 + a + b);
    b = a; a = 0;
    //if(s == 10) ++a;
  }

  return make_pair(-sum, id);
}

int main() {
  int n;
  while(cin >> n && n) {
    vector<pair<int,int> > v;
    for(int i = 0; i < n; ++i) {
      v.push_back(getScore());
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); ++i) {
      cout << v[i].second << " " << -v[i].first << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  string a;
  cin >> a;
  int i=0;
  int j=a.size()-1;
  
  while(1){
    if(a.at(i)=='A')
      break;
    else
      i++;
  }
  
  while(1){
    if(a.at(j)=='Z')
      break;
    else
      j--;
  }
  
  cout << j-i+1 << endl;
}

Measured memory_bytes: 640
from collections import defaultdict

import sys
sys.setrecursionlimit(10**6)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    k=ii()
    a,b=mis()
    x=b//k-(a-1)//k
    print('OK' if x>0 else 'NG')

if __name__ == "__main__":
    main()

Measured memory_bytes: 9384
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
typedef pair<int,int> pa;
struct Ghjattu{
    int to;
    int id;
    Ghjattu(int a,int b){
        to=a;
        id=b;
    }
};
vector<Ghjattu> G[N];
int ans[N],flag[N],cnt=0;
int n;
void BFS(){
    queue<pa> que;
    for(int i=0;i<G[1].size();i++){
        Ghjattu g=G[1][i];
        if(flag[g.id]) continue;
        flag[g.id]=1;
        cnt++;
        ans[g.id]=cnt;
        que.push(pa(g.to,ans[g.id]));
    }
    while(!que.empty()){
        pa p=que.front();
        que.pop();
        int u=p.first;
        int k=0;
        for(int i=0;i<G[u].size();i++){
            Ghjattu g=G[u][i];
            if(flag[g.id]) continue;
            k++;
            flag[g.id]=1;
            if(k!=p.second){
                ans[g.id]=k;
                //k++;
            }else{
                k++;
                ans[g.id]=k;
            }
            if(k>cnt) cnt=k;
            que.push(pa(g.to,ans[g.id]));
        }
    }
}
int main(){
    scanf("%d", &n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d %d", &u, &v);
        G[u].push_back(Ghjattu(v,i));
        G[v].push_back(Ghjattu(u,i));
    }
    BFS();
    printf("%d\n", cnt);
    for(int i=1;i<n;i++) printf("%d\n", ans[i]);
    return 0;
}


Measured memory_bytes: 7424
#[allow(unused_imports)]
use std::char::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

#[allow(unused_macros)]
macro_rules! debug {($($a:expr),*) => {println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);}}
#[allow(unused_macros)]
macro_rules! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

#[derive(PartialEq, PartialOrd)]
pub struct Total<T>(pub T);
impl<T: PartialEq> Eq for Total<T> {}
impl<T: PartialOrd> Ord for Total<T> { fn cmp(&self, other: &Total<T>) -> std::cmp::Ordering { self.0.partial_cmp(&other.0).unwrap() }}

#[allow(dead_code)]
const MAX:usize = 100006;
#[allow(dead_code)]
const INF_U32:u32 = 1 << 31;
#[allow(dead_code)]
const INF_I32:i32 = 1 << 30;
#[allow(dead_code)]
const INF_U64:u64 = 1 << 63;
#[allow(dead_code)]
const INF_I64:i64 = 1 << 62;


fn main() {
    input!{n:usize, a:[i64;n]};
    let mut map = HashMap::new();
    let mut cnt:i64 = 0;
    for i in 0..a.len() {
        if a[i] >= 3200 {
            cnt += 1;
        } else {
            let mut count = map.entry(a[i]/400).or_insert(0);
            *count += 1;
        }
    }
    //debug!(cnt, &map);
    if map.len() == 0 {
        println!("{} {}", 1, cnt);
        return ();
    }
    println!("{} {}", map.len(), map.len() as i64 +cnt);
}


Measured memory_bytes: 4352
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	H := make([]bool, 13)
	S := make([]bool, 13)
	C := make([]bool, 13)
	D := make([]bool, 13)
	for i := 0; i < n; i++ {
		var s string
		var num int
		fmt.Scan(&s, &num)
		num--
		if s == "H" {
			H[num] = true
		} else if s == "C" {
			C[num] = true
		} else if s == "D" {
			D[num] = true
		} else {
			S[num] = true
		}
	}
	for i := 0; i < len(S); i++ {
		if !S[i] {
			fmt.Printf("S %d\n", i+1)
		}
	}
	for i := 0; i < len(H); i++ {
		if !H[i] {
			fmt.Printf("H %d\n", i+1)
		}
	}
	for i := 0; i < len(C); i++ {
		if !C[i] {
			fmt.Printf("C %d\n", i+1)
		}
	}
	for i := 0; i < len(D); i++ {
		if !D[i] {
			fmt.Printf("D %d\n", i+1)
		}
	}

}



Measured memory_bytes: 1128
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <limits>
#include <string>
#include <bitset>
#include <functional>

using namespace std;
using lint = long long;
using P = pair<lint, lint>;
using V = vector<lint>;
constexpr lint MOD = 1e9 + 7;
#define rep(i, n) for (lint i = 0; i < (n); i++)
#define repr(i, n) for (lint i = (n); i > 0; i--)
#define rep1(i, n) for (lint i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define mp(x, y) make_pair((x), (y))

// int A, B, C, F, H, I, J, K, L, M, N, S, T, U, W, X, Y;
lint A, B, F, H, I, J, K, L, M, N, S, T, U, W, X, Y;
// string A, B;
lint ans = 0;
// string ans;
multiset<lint, greater<lint>> a;

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

	cin >> N >> M;
    rep(i, N) {
        cin >> A;
		a.insert(A);
    }

	rep(i, M) {
		auto it = a.begin();
		a.insert(*it / 2);
		a.erase(it);
	}
    for(auto it = a.begin(); it != a.end(); it++) {
		ans += *it;
	}

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

Measured memory_bytes: 4992
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
 
int N;
string S;
 
int main() {
    cin >> N >> S;
    int white = 0;
    for (int i = 0; i < N; i++) {
        if (S[i] == '.') white++;
    }

    int sum_bw[N+1];
    sum_bw[0] = white;
    
    for (int i = 0; i < N; i++){
        if (S[i] == '.') sum_bw[i+1] = sum_bw[i] - 1;
        else sum_bw[i+1] = sum_bw[i] + 1;
    }

    sort(sum_bw, sum_bw+N+1);
 
   cout << sum_bw[0] << endl;
 
}

Measured memory_bytes: 2036
#include<bits/stdc++.h>
#define maxn 1000000001
using namespace std;
long long read(){
    long long xx=0,flagg=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')
        ch=getchar();
    if(ch=='-'){
        flagg=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        xx=xx*10+ch-'0';
        ch=getchar();
    }
    return xx*flagg;
}
void pus(long long xx,long long flagg){
    if(xx<0){
        putchar('-');
        xx=-xx;
    }
    if(xx>=10)
        pus(xx/10,0);
    putchar(xx%10+'0');
    if(flagg==1)
        putchar(' ');
    if(flagg==2)
        putchar('\n');
    return;
}
int n,m,i,j,k,sum[2][6005],top,zhan[6005],st,ed,sum2;
int topa,topb,book[6005],booka[6005],bookb[6005];
string c[6005],p,ans;
char s[6005];
int main(){
    n=read();m=n*2;
    scanf("%s",s+1);
    for(i=1;i<=m;i++){
    	sum[0][i]=sum[0][i-1];
    	sum[1][i]=sum[1][i-1];
    	sum[s[i]-'a'][i]++;
    	if(s[i]=='a'){
    		topa++;
    		book[i]=topa;
    		booka[topa]=i;
    	}
    	else{
			topb++;
			book[i]=topb;
			bookb[topb]=i;
		}
    }
   	for(i=1;i<=m;i++)
   		if(sum[0][i]==sum[1][i]){
   			top++;
   			zhan[top]=i;
   		}
   	for(i=1;i<=top;i++){
   		st=zhan[i-1]+1;ed=zhan[i];sum2=0;
   		if(s[st]=='a'){
	   		for(j=st;j<=ed;j++){
	   			if(s[j]=='a'){
	   				j=bookb[book[j]];
	   				sum2++;
	   			}
	   		}
	   		while(sum2--){
				c[i]+='a';
				c[i]+='b';
			}
   		}
   		else{
   			for(j=ed;j>=st;j--)
   				if(s[j]=='a'){
   					for(k=st;k<=ed;k++)
   						if(book[k]>=book[j]&&book[k]<=book[ed])
   							p+=s[k];
   					if(j==ed)
   						c[i]=p;
   					else if(p>c[i])
   						c[i]=p;
   					p="";
   				}
   		}
   	}
   	for(i=top;i>=1;i--)
   		if(c[i]+ans>=ans)
   		 	ans=c[i]+ans;
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4108
#include "bits/stdc++.h"

using namespace std;

int d[110], l[110];

int main() {
	int n, x;
	cin >> n >> x;
	d[1] = 0;
	int cnt = 1;
	for(int i = 1; i <= n; i++) {
		int in;
		cin >> in;
		d[i + 1] = d[i] + in;
		if(d[i + 1] <= x) cnt++;
	}
	cout << cnt << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string A,B;
int dp[3009][3009];
int main(){
	cin>>A>>B;
	string a=" "+A;
	string b=" "+B;
	for(int i=1;i<b.size();i++){
		for(int j=1;j<a.size();j++){
			if(b[i]==a[j]){
				dp[i][j]=dp[i-1][j-1]+1;
				continue;
			}
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	int i=b.size()-1,j=a.size()-1;
	string ans;
	while(dp[i][j]!=0){
		if(dp[i][j]-1==dp[i-1][j-1] && dp[i][j]>dp[i-1][j] && dp[i][j]>dp[i][j-1]){
			ans+=b[i];
			i--;
			j--;
			continue;
		}
		int x=dp[i-1][j];
		int y=dp[i][j-1];
		if(x>y) i--;
		else j--;
	}
	reverse(ans.begin(),ans.end());
	cout<<ans<<endl;
}


Measured memory_bytes: 35584
#include <bits/stdc++.h>
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrepi(i,a,b) for(int i=((int)(b)-1);i>=(a);--i)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) rrepi(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define ZERO(x) memset(x,0,sizeof(x))
#define MINUS(x) memset(x,-1,sizeof(x))
#define UNIQUE(x) (x).erase(unique(ALL(x)), (x).end())
#define TOUPPER(x) transform(ALL(x), (x).begin(), ::toupper)
#define TOLOWER(x) transform(ALL(x), (x).begin(), ::tolower)
#define debug(var)  do{std::cout << #var << " : "; view(var);}while(0)
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){for(const auto& v : vv){ view(v); } }
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void viewarr(T arr[], int n) { for(int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll qp(ll a,ll b){ll ans=1;do{if(b&1)ans=1ll*ans*a;a=1ll*a*a;}while(b>>=1);return ans;}
ll qp(ll a,ll b,ll mo){ll ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5;

int main() {
    string S; cin >> S;
    bool ans = false;
    rep(i,3) if(S[i] == '7') ans = true;
    cout << (ans ? "Yes" : "No") << endl;
    return 0;
}



Measured memory_bytes: 3592
k, n = map(int, input().split())
la = list(map(int, input().split()))
la.sort()

ld = []
ld.append(k - la[-1] + la[0])
for i in range(1, n):
    ld.append(la[i] - la[i-1])

ld.sort()

print(k - ld[-1])


Measured memory_bytes: 26444
#include <stdio.h>
#include <limits.h>
#define N 500000
void Merge(int,int,int);
void MergeSort(int,int);
int s[N],count=0;
int main(){
  int n,i;
  scanf("%d",&n);
  for(i = 0 ; i<n ;i++){
    scanf("%d",&s[i]);
  }
  MergeSort(0,n);
  for(i = 0 ; i<n ;i++){
    if(i == n-1)  printf("%d\n%d\n",s[i],count);
    else printf("%d ",s[i]);
  }
  return 0;
}

void Merge(int left ,int mid ,int right){
  int n1,n2,i,j,k;
  n1 = mid -left;
  int L[n1];
  n2 = right - mid;
  int R[n2];

  for( i =0 ;i<=n1-1;i++){
    L[i]=s[left +i];
  }
  for( i =0 ;i<=n2-1;i++){
    R[i]=s[mid +i];
  }
  L[n1] =INT_MAX;
  R[n2] = INT_MAX;
  i=0;
  j=0;
  for(k= left ;k<=right-1;k++){
    if(L[i] <= R[j]){
      count++;
      s[k] = L[i];
      i=i+1;
    }
    else {
      count++;
      s[k] = R[j];
      j=j+1;
    }
  }
}
void MergeSort(int left ,int right){
  int mid;
  if(left +1 <right){
    mid =(left +right)/2;
    MergeSort(left,mid);
    MergeSort(mid,right);
    Merge(left,mid,right);
  }
}



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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second

using vint=vector<int>;
using pint=pair<int,int>;
using vpint=vector<pint>;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

template<class A,class B>
ostream& operator<<(ostream& ost,const pair<A,B>&p){
	ost<<"{"<<p.first<<","<<p.second<<"}";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost,const vector<T>&v){
	ost<<"{";
	for(int i=0;i<v.size();i++){
		if(i)ost<<",";
		ost<<v[i];
	}
	ost<<"}";
	return ost;
}

template<uint32_t mod>
struct ModInt{
	uint32_t a;
	ModInt& s(uint32_t vv){
		a=vv<mod?vv:vv-mod;
		return *this;
	}

	ModInt(int64_t x=0){s(x%mod+mod);}

	ModInt& operator+=(const ModInt &x){return s(a+x.a);}
	ModInt& operator-=(const ModInt &x){return s(a+mod-x.a);}
	ModInt& operator*=(const ModInt &x){
		a=uint64_t(a)*x.a%mod;
		return *this;
	}
	ModInt& operator/=(const ModInt &x){
		*this*=x.inv();
		return *this;
	}

	ModInt operator+(const ModInt &x)const{return ModInt(*this)+=x;}
	ModInt operator-(const ModInt &x)const{return ModInt(*this)-=x;}
	ModInt operator*(const ModInt &x)const{return ModInt(*this)*=x;}
	ModInt operator/(const ModInt &x)const{return ModInt(*this)/=x;}
	bool operator==(const ModInt &x)const{return a==x.a;}
	bool operator!=(const ModInt &x)const{return a!=x.a;}
	bool operator<(const ModInt &x)const{return a<x.a;}

	ModInt operator-()const{return ModInt()-*this;}
	ModInt pow(int64_t n)const{
		ModInt res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}

	ModInt inv()const{return pow(mod-2);}
};

template<uint32_t mod>
istream& operator>>(istream& in,ModInt<mod>& a){
	return (in>>a.a);
}
template<uint32_t mod>
ostream& operator<<(ostream& out,const ModInt<mod>& a){
	return (out<<a.a);
}
using mint=ModInt<1000000007>;
//using mint=ModInt<998244353>;

mint dp[111111];
bool ok[111111];

signed main(){
	int N,M;
	cin>>N>>M;
	fill_n(ok,N+1,true);
	rep(i,M){
		int a;cin>>a;
		ok[a]=false;
	}
	dp[0]=1;
	for(int i=1;i<=N;i++){
		if(!ok[i])continue;
		dp[i]+=dp[i-1];
		if(i>1)dp[i]+=dp[i-2];
	}
	cout<<dp[N]<<endl;
	return 0;
}

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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/07/07  Problem: soundhound2018_master_qual C / Link: __CONTEST_URL__  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */




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



	long double N, M, D;
	cin >> N >> M >> D;

	long double ans;
	if (D == 0) {
		ans = (M - 1) / N;
	}
	else {
		ans = 2 * (N - D)*(M - 1) / N / N;
	}
	cout << fixed << setprecision(30) << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pll pair<ll,ll>
#define sll set<ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define vpl vector<pll>
#define gll greater<ll>
#define prq priority_queue
#define mp make_pair
#define pb push_back
#define rapido ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long int ll;
typedef long double ld;
ll mx=INT_MAX;
ll mn=INT_MIN;
ll mod=1e9+7;
const ll maxs=2e6+6;
ll max2d=1e3+3;


ll v;
vll *g;
ll *p;
ll *lvl;
mll m;
ll *clr;


ll fast(ll base , ll power)
{
    ll res=1;
    while(power)
    {
        if(power&1)
            res=res*base;
        base = base*base;
        power>>=1;
    }
    return res;
}


void addEdge(ll x,ll y)
{
    g[x].pb(y);
    g[y].pb(x);
}


int main()
{
    ld l;
    cin>>l;
    
    ld ans = l/3;
    l = l - l/3;
    ans = ans * (l/2);
    l = l - l/2;
    ans = ans * l;
    
    cout<<fixed<<setprecision(12)<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,a;
  cin>>n>>a;
  ll x[n];
  ll i,j,k;
  for(i=0;i<n;i++) cin>>x[i];
  ll dp[2][n+1][50*50+100];
  memset(dp,0,sizeof(dp));
  dp[0][0][0]=1;
  for(i=0;i<n;i++){
    for(j=0;j<50*50+50;j++){
      for(k=0;k<n;k++){
	dp[(i+1)%2][k+1][j+x[i]]+=dp[i%2][k][j];
	dp[(i+1)%2][k][j]       +=dp[i%2][k][j];
	dp[i%2][k][j]=0;
      }
    }
  }
  ll ans=0;
  for(i=1;i<=n;i++) ans+=dp[n%2][i][i*a];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2304
s = input()

n = len(s)
mod = 10**9+7

dp = [[0]*13 for i in range(n+1)]
dp[0][0]=1

for i in range(n):
    if s[-1-i]=='?':
        p = [x*pow(10,i,13) for x in range(0,10)]
    else:
        p = [int(s[-1-i])*pow(10,i,13)]
    for j in range(13):
        for x in p:
            dp[i+1][(j+x)%13] += dp[i][j]
    for j in range(13):
        dp[i+1][j]%=mod

print(dp[-1][5])


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

using ll = int_fast64_t;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define repr(i,n) for(int i{n};i-->0;)
template<int64_t MOD>
struct mod_int{
  int64_t val;
  constexpr mod_int():val(0){}constexpr mod_int(int64_t x)noexcept:val(x>=0?x%MOD:(MOD-(-x)%MOD)%MOD){}
  constexpr int64_t value()const noexcept{return val;}constexpr int64_t get_MOD()const noexcept{return MOD;}
  constexpr mod_int operator+(mod_int const& rhs){return mod_int(*this)+=rhs;}
  constexpr mod_int operator-(mod_int const& rhs){return mod_int(*this)-=rhs;}
  constexpr mod_int operator*(mod_int const& rhs){return mod_int(*this)*=rhs;}
  constexpr mod_int operator/(mod_int const& rhs){return mod_int(*this)/=rhs;}
  constexpr mod_int &operator++(int _){val += 1;if(val>MOD)val-=MOD;return *this;}
  constexpr mod_int &operator++(){val += 1;if(val>MOD)val-=MOD;return *this;}
  constexpr mod_int &operator--(int _){val -= 1;if(val<0)val+=MOD;return *this;}
  constexpr mod_int &operator--(){val -= 1;if(val<0)val+=MOD;return *this;}
  constexpr mod_int &operator+=(mod_int const& rhs)noexcept{val += rhs.val;if(val>=MOD)val-=MOD;return *this;}
  constexpr mod_int &operator-=(mod_int const& rhs)noexcept{if(val<rhs.val)val+=MOD;val-=rhs.val;return *this;}
  constexpr mod_int &operator*=(mod_int const& rhs)noexcept{(val*=rhs.val)%=MOD;return *this;}
  constexpr mod_int &operator/=(mod_int rhs)noexcept{*this*=rhs.inverse();return *this;}
  constexpr mod_int operator^(int64_t n){return mpow(n);}
  constexpr mod_int operator^(mod_int n){return mpow(n.val);}
  constexpr friend std::ostream &operator<<(std::ostream& os, mod_int const& mi){return os<<mi.val;}
  constexpr friend std::istream &operator>>(std::istream& is, mod_int & mi){int64_t t=0;is>>t;mi = mod_int<MOD>(t);return is;}
  constexpr mod_int inverse(){int64_t a=val,b=MOD,u=1,v=0,t=0;while(b>0){t=a/b;std::swap(a-=t*b,b);std::swap(u-=t*v,v);}return mod_int(u);}
  constexpr mod_int mpow(int64_t n)const{mod_int res(1),e(*this);while(n){if(n&1)res*=e;e*=e;n>>=1;}return res;}
};
using mint = mod_int<1000000007>;

signed main(){

  string s;
  cin>>s;
  int n = size(s);

  vector<mint> a(n),c(n),q(n);
  rep(i,n){
    if(s[i]=='A')a[i]++;
    if(s[i]=='C')c[i]++;
    if(s[i]=='?')q[i]++;
  }
  vector<mint> as(n+1),cs(n+1),qs(n+1);
  rep(i,n){
    as[i+1] = as[i]+a[i];
    cs[i+1] = cs[i]+c[i];
    qs[i+1] = qs[i]+q[i];
  }

  mint ans = 0,base = 3;
  rep(i,n){
    if(s[i]=='A'||s[i]=='C')continue;
    mint pre_a = as[i];
    mint suf_c = cs[n]-cs[i+1];
    mint pre_q = qs[i];
    mint suf_q = qs[n]-qs[i+1];
    mint pre_aq = pre_a*(base^pre_q) + pre_q*(base^(pre_q-1));
    mint suf_cq = suf_c*(base^suf_q) + suf_q*(base^(suf_q-1));
    ans += pre_aq*suf_cq;
  }
  cout<<(ans)<<endl;

}

Measured memory_bytes: 8272
// author:-*mdragneell*

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pi  pair<int,int>
#define pl  pair<ll,ll>

int const N=105;
int const mod=1e9+7;
ll min(ll x,ll y) { if(x<y) return x; else return y; }
ll max(ll x,ll y) { if(x>y) return x; else return y; }

ll a[N],n;
ll dp[100005];
ll sol(ll k)
{
    dp[0]=1;
    ll i,j,p;
    for(i=0;i<n;i++)
    {
        vector<ll>fake(k+2);

        for(j=0;j<k;j++)
        {
            fake[j+1]+=dp[j];
            ll r=min(a[i]+j,k);

            if(r+1<=k)
            fake[r+1]-=dp[j];
        }
        for(j=1;j<=k;j++){
            fake[j]+=fake[j-1];
            fake[j]=(fake[j]%mod+mod)%mod;
        }


        for(j=0;j<=k;j++){
            dp[j]+=fake[j];
            dp[j]=(dp[j]%mod+mod)%mod;
        }
    }

    return dp[k];
}
int main()
{
    ll i,k;
    cin>>n>>k;
    for(i=0;i<n;i++) cin>>a[i];

    cout<<sol(k);
}


Measured memory_bytes: 1792
//Using vim
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;


void solve() {
	string s, t;
	cin >> s >> t;
	if(s.compare(t.substr(0, t.size() - 1)) == 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	
}


int main() {
	int cases = 1;
	//cin >> cases;
	while(cases--) {
		solve();
	}
	return 0;
}


Measured memory_bytes: 3120
X = int(input())
x2 = X % 100

if x2==0:
  print('1')
elif X<100:
  print('0')
else:
  tmp=0
  for f in range(19,0,-1):
    if 5*f==x2:
      tmp=105*f
      break
    elif 5*f<x2:
      x2 -= 5*f
      tmp = 105*f + (100 + x2)
      break
      
  if tmp>X:
    print('0')
  else:
    print('1')

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

int main() {
	int n, m, ans = 0;
	cin >> n >> m;
	//a[n]はそれぞれのスイッチがどの電球に繋がっているか
	vector<int> a(n);
	rep(i,m) {
		int k;
		cin >> k;
		// i個めの電球はk個のスイッチに繋がっている
		rep(j,k) {
			int s;
			cin >> s;
			s--;
			// s個めのスイッチにi番(bit)目の電球がつながっている
			a[s] |= 1 << i;
		}
	}
	int p = 0;
	rep(i,m) {
		int b;
		cin >> b;
		p |= b << i;
	}
	for (int i = 0; i < (1 << n); i++) {
		int t = 0;
		rep(j,n) {
			if (i >> j & 1) t ^= a[j];
		}
		if (t == p) ans++;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int a[3];
	a[0] = n%10;
	a[1] = n/10%10;
	a[2] = n/100;
	for(int i = 2; i > -1; i--)
		if(a[i] == 1)
			cout << 9;
		else if(a[i] == 9)
			cout << 1;
		else
			cout << a[i];
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i+=1)
#define reps(i,a,b) for(int i=a;i>=b;i-=1)
#define vi vector<int>
#define vvi vector<vector<int>>
#define pb push_back
#define pi pair<int, int>
#define mp make_pair
#define ff first
#define ss second
#define in1(x) int x; cin>>x;
#define in2(x, y) int x, y; cin>>x>>y;
#define in3(x, y, z) int x, y, z; cin>>x>>y>>z;
#define in4(x, y, z, w) int x, y, z, w; cin>>x>>y>>z>>w;
#define mi unordered_map<int,int>
#define mem(x) memset(x, 0, sizeof(x))
#define IOS ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define mod 1000000007
using namespace std;

//bool primes[1000001];vi prime;
//void seive(){memset(primes, true, sizeof(primes));primes[0] = primes[1] = false;for(int i = 2; i*i<=1000000;i += 1){
//if(primes[i]){for(int j = i*i; j <= 1000000;j += i) primes[j] = false;}}rep(i, 2, 1000001){if(primes[i]) prime.pb(i);}}
//int gcd(int a, int b){return b==0 ? a : gcd(b, a%b);}
//int power(int x, int y){ int res = 1;x = x % mod; if (x == 0) return 0;
//while (y > 0){ if(y & 1) res = (res*x) % mod; y = y>>1; x = (x*x) % mod;} return res;}

int32_t main(void){
	IOS;
	in4(a, b, c, d);
	in1(e);
	if(a == 0) cout<<1<<endl;
	else if(b == 0) cout<<2<<endl;
	else if(c == 0) cout<<3<<endl;
	else if(d == 0) cout<<4<<endl;
	else cout<<5<<endl;
}


Measured memory_bytes: 3628
{-# LANGUAGE OverloadedStrings #-}
import Data.Maybe
import Data.Array.IO
import Data.IORef
import qualified Data.Map as M
import Control.Monad
import qualified Data.ByteString.Char8 as BC

main :: IO ()
main = do
  [iy,ix] <- map read . words <$> getLine :: IO [Int]
  routeArr <- newArray_ ( (0,0), (iy-1,ix-1) ) :: IO (IOUArray (Int,Int) Bool)
  forM_ [0..(iy-1)] $ \ny -> do
    routesList <- BC.getLine
    forM_ [0..(ix-1)] $ \nx -> do
      case routesList `BC.index` nx of
        '.' -> writeArray routeArr (ny,nx) True -- '.'
        '#' -> writeArray routeArr (ny,nx) False -- '#'
        _ -> return ()
  times <- solve (iy-1,ix-1) routeArr
  print times

solve :: (Int,Int) -> IOUArray (Int,Int) Bool -> IO Int
solve (y,x) ioArr = do
  memo <- newIORef (M.empty)
  firstB <- readArray ioArr (0,0)
  if firstB then
    do modifyIORef memo (M.insert (0,0) 0)
    else
      modifyIORef memo (M.insert (0,0) 1)
  initial (y,x) ioArr memo
  m <- readIORef memo
  -- print m
  let v = fromJust $ M.lookup (y,x) m
  return v
  where
    initial :: (Int,Int) -> IOUArray (Int,Int) Bool -> IORef (M.Map (Int,Int) Int) -> IO ()
    initial (y,x) ioArr memo = do
      forM_ [1..y] $ \i -> do
        m <- readIORef memo
        upB <- readArray ioArr (i-1,0)
        myB <- readArray ioArr (i,0)
        let val = fromJust $ M.lookup (i-1,0) m
            v = if (not upB) || myB
                then val
                else val+1
        modifyIORef memo (M.insert (i,0) v)
      forM_ [1..x] $ \j -> do
        m <- readIORef memo
        leB <- readArray ioArr (0,j-1)
        myB <- readArray ioArr (0,j)
        let val = fromJust $ M.lookup (0,j-1) m
            v = if (not leB) || myB
                then val
                else val+1
        modifyIORef memo (M.insert (0,j) v)
      forM_ [1..y] $ \yy -> do
        forM [1..x] $ \xx -> do
          m <- readIORef memo
          upB <- readArray ioArr (yy-1,xx)
          leB <- readArray ioArr (yy,xx-1)
          myB <- readArray ioArr (yy,xx)
          let upNowVal = fromJust $ M.lookup (yy-1,xx) m
              upNextVal = if (not upB) || myB
                          then upNowVal
                          else upNowVal+1
              leftNowVal = fromJust $ M.lookup (yy,xx-1) m
              leftNextVal = if (not leB) || myB
                            then leftNowVal
                            else leftNowVal+1
          modifyIORef memo $ M.insert (yy,xx) (min upNextVal leftNextVal)


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

#define debug(n) cerr << #n << ':' << n << endl;

using namespace std;

using  ll = long long;

template<class T,class U>
using umap = unordered_map<T,U>;

template<class T>
using uset = unordered_set<T>;

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

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


int main(){
  ll n, k, q; cin >> n >> k >> q;
  ll base = k - q;
  umap<ll, ll> pt;
  for(int i = 0; i < q; ++i){
    ll x; cin >> x;
    pt[x]++;
  }
  for(int i = 1; i <= n; ++i){
    if(base + pt[i] > 0)cout << "Yes\n";
    else cout << "No\n";
  }
  return 0;
}


Measured memory_bytes: 4772
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
const ll INF = 1LL << 62;

int main() {
  //
  ll n;
  cin >> n;
  vl d(n);
  rep(i, n) cin >> d[i];
  ll ans = 0;
  rep(i, n - 1) {
    REP(j, i + 1, n) { ans += d[i] * d[j]; }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 888
#include<iostream>

using namespace std;

#define MMAX 100000
#define YES 0
#define NO 1

struct S{
	int p, q, pq;
};
int main(){

	int m, a, b;
	int hurui[MMAX + 1] = { YES };
	int prime[MMAX + 1];
	int cnt = 0;
	S ans = { -1, -1, -1 };

	hurui[0] = NO, hurui[1] = NO;
	for (int i = 2; i < MMAX; i++){
		if (hurui[i] == YES){
			prime[cnt] = i;
			cnt++;
			for (int j = i * 2; j < MMAX; j += i){
				hurui[j] = NO;
			}
		}
	}

	while (1){

		cin >> m >> a >> b;
		if (a == 0 && b == 0 && m == 0) break;

		for (int i = 0; m >= prime[i] * prime[0]; i++){
			for (int j = 0; m >= prime[i]*prime[j]; j++){
				if ((double)prime[i] / prime[j] >= (double)a / b && (double)prime[i] / prime[j] <= 1){
					if (ans.pq < prime[i] * prime[j]){
						ans.p = prime[i], ans.q = prime[j], ans.pq = prime[i] * prime[j];
					}
				}
			}
		}
		cout << ans.p << " " << ans.q << endl;
		ans.p = -1, ans.q = -1, ans.pq = -1;
	}
	return 0;
}

Measured memory_bytes: 1600
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    long long x,sum=0,a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]==0)
        {
            if(sum%2==1)
                --sum;
        }
        sum+=a[i];
    }

    cout<<sum/2;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000007LL;
constexpr int inf = 1000000007;

inline string gender(int x) {
    cout << x << endl;
    string t;
    cin >> t;
    return t;
}

int main() {
    int n;
    cin >> n;
    int l = 0, r = n - 1;
    string gender_l = gender(l);
    if (gender_l == "Vacant")
        return 0;
    string gender_r = gender(r);
    if (gender_r == "Vacant")
        return 0;

    while (r - l > 1) {
        int m = (l + r) / 2;
        string gender_m = gender(m);
        if (gender_m == "Vacant")
            return 0;

        int len = m - l + 1;
        if (len % 2 != 0) {
            if (gender_l == gender_m) {
                l = m;
                gender_l = gender_m;
            } else {
                r = m;
                gender_r = gender_m;
            }
        } else {
            if (gender_l == gender_m) {
                r = m;
                gender_r = gender_m;
            } else {
                l = m;
                gender_l = gender_m;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 852
n, m, k = map(int, input().split())

par = [-1 for _ in range(n)]

def find(x):
    if par[x] < 0:
        return x
    par[x] = find(par[x])
    return par[x]

def union(x, y):
    x, y = find(x), find(y)
    if x == y:
        return
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

def same(x, y):
    return find(x) == find(y)

def size(x):
    return -par[find(x)]

ans = [-1]*n
for i in range(m):
    a, b = map(int, input().split())
    union(a-1, b-1)
    ans[a-1] -=1
    ans[b-1] -=1

for j in range(k):
    c, d = map(int, input().split())
    if same(c-1, d-1):
        ans[c-1] -=1
        ans[d-1] -=1

for i in range(n):
    ans[i] += size(i)

print(*ans)

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

int main()
{
	int n;cin>>n;
	
	int h[n+1];
	
	for(int i=0;i<n;i++)
	cin>>h[i];
	
	int dp[100001];
	
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);
	for(int i=2;i<n;i++)
	dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
	
	cout<<dp[n-1];
	
	return 0;
}

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

int main(){
    stack<int> S;
    string s;
    int a,b;
    while(cin>>s){
        if(s=="+"){a=S.top();S.pop();b=S.top();S.pop();S.push(a+b);}
        else if(s=="-"){a=S.top();S.pop();b=S.top();S.pop();S.push(b-a);}
        else if(s=="*"){a=S.top();S.pop();b=S.top();S.pop();S.push(a*b);}
        else S.push(atoi(s.c_str()));
    }
    printf("%d\n",S.top());
}


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

bitset<10> possibleSwitch; 

int count(vector<int> index){
	int temp=0;
	for(int i: index){
		temp+=possibleSwitch[i];
	}
	return temp;
} 

int main() {
	int n, m, ans = 0;
	cin >> n >> m;
	vector<vector<int>> bulb;
	vector<int> bulbCondition;
	for(int i = 0, k; i<m; i++){
		cin >> k;
		vector<int> temp;
		for(int j = 0, con; j<k; j++){
			cin >> con;
			temp.push_back(con-1);
		}
		bulb.push_back(temp);
	}
	for(int i = 0, k; i<m; i++){
		cin >> k;
		bulbCondition.push_back(k);
	}

	bool check;
	for(int i = 0, k; i<1<<n; i++){
		possibleSwitch = i;
		check = true;
		for(int j = 0; j<m; j++){
			k = count(bulb[j]);
			if(k%2 != bulbCondition[j]){
				check = false;
				break;
			}
		}

		if(check){
			ans++;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 384
/// kAAzuki Hoshino
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

 
int n;
int a[50];
pair<int,int> b[55][55];

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
  
  cin >> n;
  for(int i=0;i<n;i++)
  {
    cin >> a[i];
    for(int j=1;j<=a[i];j++){
      cin >> b[i][j].fs >> b[i][j].sc;
      b[i][j].fs--;
    }
  }
  int ans = 0;
  for(int i=0;i<(1<<n);i++){
    bool flag = true;
    for(int j=0;j<n;j++){
      if( i&(1<<j) ){
        for(int k=1;k<=a[j];k++){
          if(b[j][k].sc==0){
            if( i & (1<<(b[j][k].fs)) )flag = false;
          }
          if(b[j][k].sc==1){
            if( i & ( 1<<(b[j][k].fs) ) );
            else flag = false;
          }
        }
      }
    }
    if(flag){
      //cout << i << endl;
      ans = max(ans, (int)__builtin_popcount(i) );
    }
  }
  cout << ans << endl;

return 0;
}
///....


Measured memory_bytes: 256
h,w,k=map(int,input().split())
c=[input() for i in range(h)]
ans=0
for a in range(1<<h):
    for b in range(1<<w):
        cnt=0
        for i in range(h):
            if a>>i&1:
                continue
            for j in range(w):
                if b>>j&1:
                    continue
                cnt+=c[i][j]=='#'
        ans+=cnt==k
print(ans)

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

using namespace std;
typedef long long ll;
const int INF = (1<<30);

int n;
int f[100][10];
int p[100][11];
int cnt[100];

int main(){
    cin >> n;
    for(int i=0;i<n;++i){
        for(int j=0;j<10;++j){
            cin >> f[i][j];
        }
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<11;++j){
            cin >> p[i][j];
        }
    }
    int ret = -INF;
    for(int i=1;i<(1<<10);++i){
        int temp = i; int temp2 = 0;
        for(int m=0;m<n;++m)cnt[m] = 0;
        //10種類の時間帯で調べる
        for(int j=0;j<10;++j){
            if(temp>>j & 1){
                //それぞれの店舗が営業しているか
                for(int k=0;k<n;++k){
                    if(f[k][j]==1)cnt[k]++;
                }
            }
            
        }
        for(int l=0;l<n;++l){
                temp2 += p[l][cnt[l]];
                //cout << temp2 << endl;
            }
        //if(ret < temp2)cout << "i:" << i << endl;
        ret = max(ret,temp2);
    }
    cout << ret << endl;
    return 0;
}

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

#define PI 3.14159265358979323846264338327950L

int main(void)
{
    int A, B, H, M;
    cin >> A >> B >> H >> M;

    long double t;
    long double ans;

    t = -(long double)11 / 360.0 * PI * (long double)(H * 60 + M);

    ans = (long double)(pow(A, 2) + pow(B, 2)) - (long double)(2 * A * B * cosl(t));

    printf("%20.20Lf\n", sqrt(ans));

    return 0;
}


Measured memory_bytes: 3528
#include<stdio.h>
#include<algorithm>
int p[3];
using namespace std;
int main(){
	int a=0,b=0,c=0,d=0;
	while(~scanf("%d%d%d",p,p+1,p+2)){
		std::sort(p,p+3);
		if(p[0]+p[1]<=p[2]){
			printf("%d %d %d %d\n",a,b,c,d);
			return 0;
		}
		a++;
		if(p[0]*p[0]+p[1]*p[1]==p[2]*p[2])b++;
		if(p[0]*p[0]+p[1]*p[1]>p[2]*p[2])c++;
		if(p[0]*p[0]+p[1]*p[1]<p[2]*p[2])d++;
	}
}

Measured memory_bytes: 1040
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define Ifor(i, a, b) for (int i = int(a); i < int(b); i++)
#define Dfor(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define Trav(e, v) for (auto& e : v)
#define pb push_back
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<ii>;
template <typename T> bool ckmin (T& a, T b) { return (b < a) ? a = b, 1 : 0; }
template <typename T> bool ckmax (T& a, T b) { return (b > a) ? a = b, 1 : 0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (const string& e_) { return "\"" + e_ + "\""; }
string to_string (char e_) { return "\'" + string(1, e_) + "\'"; }
string to_string (bool e_) { return e_ ? "true" : "false"; }
template <typename T> string to_string (T e_) {
	string s_ = "[ ";
	for (const auto& x_ : e_) s_ += to_string(x_) + " ";
	return s_ + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e_) {
	return "(" + to_string(e_.first) + ", " + to_string(e_.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
 	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	int n;
	cin >> n;
	vi a(n), b(n), c(n);
	Trav(x, a) cin >> x;
	Trav(x, b) cin >> x;
	Trav(x, c) cin >> x;
	sort(all(a));
	sort(all(b));
	sort(all(c));
	ll ans = 0;
	Ifor(i, 0, n) {
		ll x = (ll)(lower_bound(all(a), b[i]) - begin(a));
		ll y = (ll)(end(c) - upper_bound(all(c), b[i]));
		ans += x * y;
	}
	cout << ans << '\n';
}



Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#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;

signed main(){
    int x, a, b;
    cin >> x >> a >> b;
    if((b - a) <= 0) cout << "delicious" << endl;
    else if((b - a) <= x) cout << "safe" << endl;
    else cout << "dangerous" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

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

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

int main() {
  int N, L;
  cin >> N >> L;
  vector<string> S(N);
  rep(i, N) cin >> S[i];
  sort(all(S));

  string ans;
  rep(i, N) {
    ans += S[i];
  }
  cout << ans << endl;
}

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

int GCD(int a,int b){
  if(b==0){
  	return a;
  }else{
  	return GCD(b,a%b);
  }
}

int main() {
  int N,X;cin>>N>>X;
  int D;cin>>D;
  D=abs(X-D);
  for(int i=1;i<N;i++){
    int d;cin>>d;
    d=abs(X-d);;
    D=GCD(d,D);
  }
  cout<<D<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  int p[n];
  for(int i = 0; i < n; i++){
  	cin >> p[i];
  }
  int count = 0;
  for(int i = 1; i < n-1; i++){
  	if((p[i-1] < p[i] && p[i] < p[i+1]) || (p[i-1] > p[i] && p[i] > p[i+1])){
    	count++;
    }
  }
  
  cout << count << endl;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

type Work struct {
	Time  int
	Limit int
}

type Works []Work

func (w Works) Len() int {
	return len(w)
}

func (w Works) Swap(i, j int) {
	w[i], w[j] = w[j], w[i]
}

func (w Works) Less(i, j int) bool {
	return w[i].Limit < w[j].Limit
}

func main() {
	n, _ := strconv.Atoi(nextLine())
	works := Works{}
	for i := 0; i < n; i++ {
		ab := strings.Fields(nextLine())
		a, _ := strconv.Atoi(ab[0])
		b, _ := strconv.Atoi(ab[1])
		works = append(works, Work{Time: a, Limit: b})
	}

	sort.Sort(works)

	time := 0
	isCan := true
	for i := range works {
		time += works[i].Time
		if time > works[i].Limit {
			isCan = false
			break
		}
	}
	if isCan {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
int main(int argc, char* argv[]) {
    int n;
    cin >> n;
    vint l(n);
    rep(i,n) cin >> l[i];
    sort(ALL(l));
    if(l[l.size()-1] < (accumulate(ALL(l),0)-l[l.size()-1])) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


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

int main(){
  int h, w, d, q, a;
  cin >> h >> w >> d;
  int di[h*w+1] = {}, dj[h*w+1] = {};
  int dist[h*w+1] = {};
  for(int i = 0; i < h; i++){
    for(int j = 0; j < w; j++){
      cin >> a;
      di[a] = i; dj[a] = j;
    }
  }
  for(int i = d+1; i <= h * w; i++){
    dist[i] = dist[i-d] + abs(di[i] - di[i-d]) + abs(dj[i] - dj[i-d]);
  }
  cin >> q;
  for(int i = 0; i < q; i++){
    int l, r;
    cin >> l >> r;
    cout << dist[r] - dist[l] << endl;
  }
  return 0;
}


Measured memory_bytes: 2176