akhauriyash/Code-Regression huggingface dataset:
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;  typedef long long ll;
inline int qr(){
	int ret=0,f=0,c=getchar();
	while(!isdigit(c)) f|=c==45,c=getchar();
	while( isdigit(c)) ret=ret*10+c-48,c=getchar();
	return f?-ret:ret;
}
const int maxn=1e5+5;
int data[maxn],n;
ll dp[maxn][3];

int main(){
	memset(dp,0xcc,sizeof dp);
	n=qr();
	for(int t=1;t<=n;++t) data[t]=qr();
	dp[0][0]=0;
	for(int t=1;t<=n;++t)
		if(data[t]>0){
			dp[t][0]=max({dp[t][0],dp[t-1][0]+data[t],dp[t-1][1]+data[t],dp[t-1][2]+data[t]});
			dp[t][1]=max({dp[t][1],dp[t-1][1]-data[t],dp[t-1][2]-data[t]});
			dp[t][2]=max({dp[t][2],dp[t-1][2]+data[t]});
		}else{
			data[t]=-data[t];
			dp[t][0]=max({dp[t][0],dp[t-1][0]-data[t],dp[t-1][1]-data[t],dp[t-1][2]-data[t]});
			dp[t][1]=max({dp[t][1],dp[t-1][0]-data[t],dp[t-1][1]+data[t],dp[t-1][2]+data[t]});
			dp[t][2]=max({dp[t][2],dp[t-1][1]+data[t],dp[t-1][2]+data[t]});
		}
	cout<<max({dp[n][0],dp[n][1],dp[n][2]})<<endl;
	return 0;	
}

//asdujoifszahikuj

Measured memory_bytes: 2944
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <functional>

using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
int S[2000];
int T[2000];
long DP[2001][2001];
void Calc(){
	int N = rei();
	int M = rei();
	for(int i=0;i<N;i++){
		S[i] = rei();
		DP[i][0] = 1;
	}
	for(int i=0;i<M;i++){
		T[i] = rei();
		DP[0][i] = 1;
	}
	DP[N][0] = 1;
	DP[0][M] = 1;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + mod;
			if(S[i-1] == T[j-1]){
				DP[i][j] += DP[i-1][j-1];
			}
			DP[i][j] %= mod;
		}
	}
	cout << DP[N][M] << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 31616
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using u64 = uint_fast64_t;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
//constexpr long long MOD = 998244353;
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }
inline int popcount(int x) {return __builtin_popcount(x);}
inline int popcount(long long x) {return __builtin_popcountll(x);}
void print() { cout << "\n"; }
template<class T, class... Args>
void print(const T &x, const Args &... args) {
    cout << x << " ";
    print(args...);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<string> S = {"AC", "WA", "TLE", "RE"};
    vector<int> ans(4);
    rep(i,N) {
        string T; cin >> T;
        rep(j,4) if (S[j]==T) ans[j]++;
    }

    rep(i,4) {
        cout << S[i] << " x " << ans[i] << ln;
    }
}

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

int main() {
  int N, K;
  cin >> N;
  cin >> K;

  int a = 1;
  rep(i, N) {
    if (a <= K) {
      a *= 2;
    } else {
      a += K;
    }
  }
  cout << a << endl;
}

Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.container, std.range;

void main()
{
    auto hw = readln.split.to!(int[]);
    auto H = hw[0];
    auto W = hw[1];

    auto M = new int[][](H, W);
    foreach (i; 0..H) foreach (j, a; readln.split.to!(int[])) M[i][j] = a;
    foreach (i; 0..H) foreach (j, b; readln.split.to!(int[])) M[i][j] = abs(M[i][j] - b);

    auto max_d = 80*(H+W);
    auto DP = new int[][][](H, W, max_d+1);
    foreach (ref dp1; DP) foreach (ref dp2; dp1) dp2[] = -1;
    int solve(int i, int j, int d) {
        if (i == H-1 && j == W-1) return abs(d - M[i][j]);
        if (DP[i][j][d] == -1) {
            auto d1 = d + M[i][j];
            auto d2 = abs(d - M[i][j]);
            if (d1 > max_d) d1 = d2;
            int r = max_d;
            if (i < H-1) {
                r = min(r, solve(i+1, j, d1));
                r = min(r, solve(i+1, j, d2));
            }
            if (j < W-1) {
                r = min(r, solve(i, j+1, d1));
                r = min(r, solve(i, j+1, d2));
            }
            DP[i][j][d] = r;
        }
        return DP[i][j][d];
    }
    writeln(solve(0, 0, 0));
}

Measured memory_bytes: 336848
#include <bits/stdc++.h>
#define mod ((ll)1e9+7)
using namespace std;
typedef long long ll;
ll n,d,x,dp[2001][2001],K[2001];

ll mod_pow(ll x,ll n){
  ll res=1;
  while(n){
    if(n%2) res=res*x%mod;
    x=x*x%mod;
    n/=2;
  }
  return res;
}

ll nCr(ll n,ll r){
  ll N=1; 
  for(int i=0;i<r;i++,n--) N=(N*(n%mod))%mod;
  ll R=mod_pow(K[r],mod-2);

  return N*R%mod;
}

int main(){
  K[0]=1;
  for(int i=1;i<=2000;i++)K[i]=(K[i-1]*i)%mod;
  
  while(1){
    cin>>n>>d>>x;
    if(!n&&!d&&!x) break;

    memset(dp,0,sizeof(dp));  
    for(int i=0;i<x;i++) dp[0][i]=1;

  
    for(int i=1;i<=min(d,n);i++){
      ll sum=0;
      for(int j=i+1;j<=n;j++){
	if(j-x>=i)sum=(sum-dp[i-1][j-x]+mod)%mod;
	sum=(sum+dp[i-1][j-1])%mod; 
	dp[i][j]=sum;
      }
    }
    
    ll ans=0;
    for(int i=0;i<min(d,n);i++)if(dp[i][n]) ans=(ans+dp[i][n]*nCr(d,i+1)%mod)%mod;
      cout <<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 32460
fun main() {
    val (k, s) = nextIntList()
    val ans = solve(k, s)
    println(ans)
}


fun solve(k: Int, s: Int): Int {
    return (0..k).flatMap { first ->
        (0..k).filter { second ->
            s - first - second in 0..k
        }
    }.count()
}

fun nextInt(): Int {
    return readLine()!!.toInt()
}

fun nextIntList(): List<Int> {
    return readLine()!!.split(" ").map { it.toInt() }
}

Measured memory_bytes: 181792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ll A,B,C,K;
    cin >> A >> B >> C >> K;
    if (K % 2 == 0) cout << A - B << endl;
    else cout << B - A << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define rep(i, n)    for(ll i = 0; i < (n); ++i)
#define repA(i, a, n)  for(ll i = a; i <= (n); ++i)
#define repD(i, a, n)  for(ll i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
#define unique_sort(x) (sort(x.begin(), x.end()), x.resize(distance(x.begin(), unique(x.begin(), x.end()))))
#define fill(a)  memset(a, 0, sizeof (a))
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
const ll mod = 1e9+7;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll tt=1;
        // cin >> tt;
    while((tt)--){
        ll n; cin >> n;
        vll v(n);
        rep(i,n){
            cin >> v[i];

        }
        int f=0;
        rep(i,n){
            if(v[i]%2==0 and (v[i]%3!=0 and v[i]%5!=0)){
                f=1; break;
            }
        }
        if(!f){
            cout << "APPROVED" << endl;
        }else{
            cout << "DENIED" << endl;
        }
    }
}


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

typedef unsigned long long UL;
typedef long long LL;
#define LP(i, a, b) for (int i = int(a); i < int(b); i++)
#define LPE(i, a, b) for (int i = int(a); i <= int(b); i++)
typedef pair<int, int> PII;
//typedef vector<vector<PII> > WAL;
typedef vector<vector<int> > SAL;
#define Ep 1e-7

#define INF 1e9

int const MaxSize = 1e5 + 10;
bool visited[MaxSize][11];

int n, qv[MaxSize], qd[MaxSize], qc[MaxSize];
int fc[MaxSize];

SAL g;

void paint(int v, int d, int c) {
	if (visited[v][d])
		return;

	visited[v][d] = true;

	if (!fc[v])
		fc[v] = c;

	if (d == 0)
		return;

	LP(i, 0, g.at(v).size())
	{
		int next = g.at(v)[i];

		paint(next, d - 1, c);

	}
}

int main() {

	ios_base::sync_with_stdio(false);
	//freopen("/Users/george/A_1.in", "r", stdin);

	int m;
	cin >> n >> m;

	g = SAL(n + 1);

	LP(i, 0 , m)
	{
		int u, v;
		cin >> u >> v;
		g.at(u).push_back(v);
		g.at(v).push_back(u);
	}

	int q;
	cin >> q;

	LP(i, 0, q)
	{
		cin >> qv[i] >> qd[i] >> qc[i];
	}

	for (int i = q - 1; i >= 0; i--) {
		paint(qv[i], qd[i], qc[i]);
	}

	LPE(i, 1, n)
	{
		cout << fc[i] << endl;
	}

	return 0;
}


Measured memory_bytes: 9208
import sys
a='abcdefghijklmnopqrstuvwxyz'
for b in sys.stdin:
 for i in range(26):
  c=''.join(a[ord(e)-97-i]if e in a else e for e in b)
  if any(('the'in c,'this'in c,'that'in c)):print(c.strip())


Measured memory_bytes: 5568
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
typedef long double ld;
#define pb push_back
#define fi first
#define se second
const ll mod = 1e9+7;
const int N = 2e5+6;
ll pre[N];
ll suf[N];
void solve(){
	int n; 
	cin>>n; 
	string s; 
	cin>>s;
	for(int i=1;i<=n;i++){
		pre[i] = pre[i-1];
		if(s[i-1]=='W'){
			pre[i]++;
		}
	}
	for(int i=n;i>=1;i--){
		suf[i] = suf[i+1];
		if(s[i-1]=='R'){
			suf[i]++;
		}
	}
	ll ans = 1e6;
	for(int i=0;i<=n;i++){
		ans = min(ans,max(pre[i],suf[i+1]));
	}
	cout<<ans<<endl;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1; 
//	cin>>t; 
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 6900
import java.util.HashMap;
import java.util.Scanner;

public class Main {

	int n, m, a;
	int h, p, q;

	public class Pair {
		int h;
		int from;

		Pair(int h, int from) {
			this.h = h;
			this.from = from;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Pair) {
				Pair p = (Pair) obj;
				return this.h == p.h && this.from == p.from;
			}
			return false;
		}
		@Override
		public int hashCode() {
			return this.h+from*37;
		}
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		while (true) {
			n = sc.nextInt();
			m = sc.nextInt();
			a = sc.nextInt();
			if (n == 0 && m == 0 && a == 0) {
				break;
			}

			HashMap<Pair, Integer> nodes = new HashMap<Main.Pair, Integer>();

			for (int i = 0; i < m; i++) {
				h = sc.nextInt();
				p = sc.nextInt();
				q = sc.nextInt();
				nodes.put(new Pair(h, p), q);
				nodes.put(new Pair(h, q), p);
			}
			int now = a;
			for (int i = 999; i >= 0; i--) {
				Pair pair = new Pair(i, now);
				if (nodes.containsKey(pair)) {
					now = nodes.get(pair);
				}
			}
			pr(now);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	public static void pr(Object o) {
		System.out.println(o);
	}

	public static void pr() {
		System.out.println();
	}
}

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

int main()
{
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    // x3
    cout << x2 - (y2 - y1) << " ";
    // t3
    cout << y2 + (x2 - x1) << " ";
    // x4
    cout << x1 - (y2 - y1) << " ";
    // y4
    cout << y1 + (x2 - x1) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

bool isprime(int x);

int main()
{
	int n, num[10000];
	int i, j;
	int ans = 0;
	
	cin >> n;
	
	for (i = 0; i < n; i++){
		cin >> num[i];
		if (isprime(num[i]) == true) ans++;
	}
	
	cout << ans << "\n";
	
	return (0);
}

bool isprime(int x)
{
	int i = 3;
	
	if (x == 2) return (true);
	
	if (x < 2 || x % 2 == 0) return (false);
	
	while (x >= i * i){
		if (x % i == 0) return (false);
		i += 2;
	}
	
	return (true);
}


Measured memory_bytes: 3108
/*#include<bits/stdc++.h>
using namespace std;
//#define p 3.14159265358979323846264338327950288419

int main(){
    int A, B, H, M;
    double x,y,C;
    cin >>A>>B>>H>>M;
    x=H*30+M/2;
    y=M*6;
    if(x<=y&&y-x<=180) C=sqrt(A*A+B*B-2*A*B*cos((y-x)*M_PI/180));
    else if(x<=y&&y-x>=180) C=sqrt(A*A+B*B-2*A*B*cos((360-y+x)*M_PI/180));
    else if(x>=y&&x-y<=180) C=sqrt(A*A+B*B-2*A*B*cos((x-y)*M_PI/180));
    else if(x>=y&&x-y>=180) C=sqrt(A*A+B*B-2*A*B*cos((360-x+y)*M_PI/180));
    

    cout << fixed << setprecision(20) << C << endl;
}*/

#include <iostream>
#include <cmath>
using namespace std;
int main() {
  int a,b,h,m;
  cin>>a>>b>>h>>m;
  double ans=sqrt(a*a+b*b-2*a*b*cos((h*60-11*m)*3.14159265358979323846/360));
  printf("%.10lf\n", ans);
}


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

int field[50+2][50+2];
int dx[8]={0,1,1,1,0,-1,-1,-1};
int dy[8]={-1,-1,0,1,1,1,0,-1};

int rec(int x, int y)
{
  int i;

  if(field[x][y]!=1) return 0;
  field[x][y] = 0;
  for(i=0;i<8;i++) rec(x+dx[i],y+dy[i]);
  return 1;
}

int main()
{
  int w,h;
  int i,j;
  int n;
  while(cin>>w>>h,w|h){
    for(j=1;j<=h;j++)
      for(i=1;i<=w;i++)
	cin>>field[i][j];
    for(j=1;j<=h+1;j++)
      field[w+1][j]=0;
    for(i=1;i<=w+1;i++)
      field[i][h+1]=0;

    n = 0;
    for(j=1;j<=h;j++) for(i=1;i<=w;i++) n += rec(i,j);

    cout<<n<<endl;
  }
}

Measured memory_bytes: 0
function Main(input) {
    var S = parseInt(input);
    var h = parseInt(S / 3600); //秒を時間へ　1時間=60分　60分=3600秒
    var x = S % 3600;
    var m = parseInt( x / 60);
    var z = x % 60;
    var s = z; 

    var answer = h + ":" + m + ":" + s;
    console.log(answer);
}
// "実行する"ボタンを押した時に実行される関数 (デバッグ用)
function debug() {
    var input = document.getElementById("input").value;
    Main(input);
}

//* この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 15136
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>

using namespace std;
using ll = long long;


int main() {
    ll n,v;
    cin >> n;
    ll g[100001]={},k[100001]={};
    for(ll i=0;i<n;i++){
         cin >> v;
         if(i%2==0) k[v]++;
         else g[v]++;
    }
    ll m1=0,m2=0,n1,n2;
    for(ll i=1;i<=100000;i++){
        if(m1<=k[i]){
            m1 = k[i];
            n1 = i;
        }
        if(m2<=g[i]){
            m2 = g[i];
            n2 = i;
        }
    }
    if(n1==n2){
        ll m11=0,m22=0,n11,n22;
        k[n1]=0,g[n2]=0;
        for(ll i=1;i<=100000;i++){
            if(m11<=k[i]){
                m11 = k[i];
                n11 = i;
            }
            if(m22<=g[i]){
                m22 = g[i];
                n22 = i;
            }
        }
        cout << min(n-m1-m22,n-m11-m2) << endl;
    }
    else{
        cout << n-m1-m2 << endl;
    }
	return 0;
}

Measured memory_bytes: 1792
unittest
{
	assert( [ "3", "1 2 2", "2 3 1" ].parse.expand.solve == "0\n0\n1" );
//	assert( [ "5", "2 5 2", "2 3 10", "1 3 8", "3 4 2" ].parse.expand.solve == "1\n0\n1\n0\n1" );
	assert( [ "5", "2 5 2", "2 3 10", "1 3 8", "3 4 2" ].parse.expand.solve == "0\n0\n0\n0\n0" );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	auto uvws = new long[][]( n - 1, 3 );
	foreach( ref uvw; uvws )
	{
		input.popFront;
		uvw = input.front.split.to!( long[] );
	}
	return tuple( n, uvws );
}

auto solve( long n, long[][] uvws )
{
	auto bws = new Tuple!( long, long )[][]( n );
	foreach( ref uvw; uvws )
	{
		uvw[ 0 ]--;
		uvw[ 1 ]--;
		bws[ uvw[ 0 ] ] ~= tuple( uvw[ 1 ], uvw[ 2 ] );
		bws[ uvw[ 1 ] ] ~= tuple( uvw[ 0 ], uvw[ 2 ] );
	}
	
	auto cs = new byte[]( n );
	cs[ 1 .. $ ] = -1;
	
	auto queue = [ 0L ];
	while( !queue.empty )
	{
		auto t = queue.front;
		queue.popFront();
		foreach( bw; bws[ t ] )
		{
			if( 0 <= cs[ bw[ 0 ] ] ) continue;
			if( bw[ 1 ] % 2 == 0 ) cs[ bw[ 0 ] ] =  cs[ t ];
			else                   cs[ bw[ 0 ] ] = !cs[ t ];
			queue ~= bw[ 0 ];
		}
	}
	
	return cs.to!( string[] ).join( "\n" );
}


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

#define N 3005

int dp[N][N*2], ap[N][N][2];

int n, X, f[N]={1,1}, rf[N]={1,1}, iv[N]={1,1};

const int mod = 998244353;

int add(int &a, int b) {
	a += b;
    if (a >= mod) a -= mod;
}
int sub(int &a, int b) {
    a -= b;
    if (a < 0) a += mod;
}
int C(int n, int k) {
	return 1ll * f[n] * rf[k] % mod * rf[n-k] % mod;
}

int main() {
    for (int i = 2; i < N; i ++) {
        f[i] = 1ll * f[i-1] * i % mod;
        iv[i] = 1ll * (mod/i) * (mod-iv[mod%i]) % mod;
        rf[i] = 1ll * rf[i-1] * iv[i] % mod;
    }
    ap[0][0][0] = 1;
    scanf("%d %d", &n, &X);
    if (X == 1) {
		int res = 1;
        for (int i = 1; i <= n; i ++) {
			res <<= 1;
			if (res >= mod) res -= mod;
        }
        printf("%d\n", res);
        return 0;
    }
    int up = X>>1;
    for (int d = 1; d <= n; d ++) {
        ap[d][0][0] = d+1;
        for (int e = 1; e <= up; e ++) {
            add(ap[d][e][0], ap[d-1][e][0]);
            add(ap[d][e][0], ap[d-1][e][1]);
            add(ap[d][e][1], ap[d-1][e-1][0]);
            add(ap[d][e][1], ap[d-1][e][1]);
        }
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= X; j ++) if (dp[i-1][j]) {
			add(dp[i][j+2], dp[i-1][j]);
            add(dp[i][j+1], dp[i-1][j]);
            add(dp[i][j], dp[i-1][j]);
        }
    }
    int ans = 0;
    for (int i = 0; i < X; i ++) add(ans, dp[n][i]);
    if (X&1) {
        int K = X;
        for (int i = K; i <= n; i ++) add(ans, C(n, i));
    }
    for (int l = 0; l <= n-2; l ++) {
        for (int s = 0; s <= X-3; s ++) {
            int sum = X-3-s;
            if (sum&1) continue;
            int d = sum>>1;
            add(ans, 1ll * dp[l][s] * ap[n-l-2][d][0] % mod);
        }
    }
    printf("%d\n", ans);
    return 0;
}


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

int sumdigit(int x){
    int count =0;
    while(x>0){
        count++;
        x/=10;
    }
    return count;
}


int main() {
    int N,M;
    cin>>N>>M;
  
    vector<int>s(M);
    vector<int>c(M);
    rep(i,M){
        cin>>s[i]>>c[i];
    }
    if(M==0&&N==1){
        cout<<0<<endl;
        return 0;
    }
      else if(M==0){
        cout<<pow(10,N-1)<<endl;
        return 0;
    }
    rep(i,M){
          if(N>=2&&s[i]==1 && c[i]==0){
            cout<<-1<<endl;
            return 0;
        }
        else if(N==1&&s[i]==1 && c[i]==0){
            cout<<0<<endl;
            return 0;
        }
    }
    
    rep(i,M){
        rep(j,M){
            if(s[i]==s[j] && c[i]!=c[j]){
                cout<<-1<<endl;
                return 0;
            }
        }
    }
    map<int,int>mp;
    rep(i,M){
        mp[s[i]]=c[i];
    }
    int sum=0;
    for(auto p:mp){
       sum+= pow(10,(N-p.first))*p.second;
    }
    if(sumdigit(sum)!=N){
        cout<<pow(10,N-1)+sum<<endl;
    }
   else cout<<sum<<endl;
}

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

#ifdef LOCAL
#include "debug.h"
#else
#define DEBUG(...)
#endif

constexpr long long lim = 1e18;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  long long res = 1;
  while (n--) {
    long long a;
    cin >> a;
    if (a == 0) {
      res = 0;
      break;
    }
    if (res == -1) continue;
    if (res <= lim / a) {
      res *= a;
    } else {
      res = -1;
    }
  }
  cout << res << '\n';
}


Measured memory_bytes: 3656
#include<iostream>
using namespace std;
int main(){
int H,W,i,j;
for(;;){
	
	cin>>H>>W;if(H==0&&W==0){ break ;}
for(i=0;i<H;i++){
	for(j=0;j<W;j++){
		
				cout<<"#";}
{		cout<<endl;
}	
}cout<<endl;
}


return 0;
}


Measured memory_bytes: 3080
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;

int h,w,x;
char s[1000][1000];
bool visited [1000][1000];
pair<int,int> start,goal;
queue<pair<int,pair<int,int>>> q;
vector<pair<int,int>> ino;

int main(){
  string a,b,c,d;cin >>a>>b>>c>>d;
  reverse(a.begin(),a.end());
  if(a==b){
    cout << "YES" << endl;
  }else{
    cout << "NO";
  }
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
  
using namespace std;
  
template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  
#define pb push_back
#define mp make_pair
#define cotu cout
#define itn int
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
#define setp(x) fixed << setprecision(x)
#define ordered_set tree<int , null_type,less<int >, rb_tree_tag,tree_order_statistics_node_update> 
  
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
  
const int inf = int(1e9);
const int mod = inf + 7;
const int N = 1e6 + 555; // TL MB
const double PI = acos(-1.0);
void mul(ll &x, ll y){
	x *= y;
	if(x >= mod) x %= mod;
}
 
void add(ll &x, ll y){
	x += y;
	if(x >= mod) x -= mod;
	if(x < 0) x += mod;
}
ll bp(ll a, ll n){
	ll r = 1;
	while(n){
		if(n & 1) mul(r, a);
		mul(a, a);
		n >>= 1;
	}
 	return r;
}
vector<pii> vals[2];

void solve()
{
	int n;
	cin >> n;
	map<int, int> cnt[2];
	int ans = inf;
	rep(i, n) {
		int x; cin >> x; cnt[i % 2][x]++;
	}
	rep(i, 2){
		int res = 0;
		for(auto it : cnt[i % 2]) {
			vals[i % 2].pb({it.S, it.F});
		}
		sort(vals[i % 2].rbegin(), vals[i % 2].rend());
	}
	for(int i = 0; i < 2; ++i)
	{
		int x = n / 2 - vals[i][0].F, y = n / 2;
		if(vals[i][0].S == vals[i ^ 1][0].S){
			if(sz(vals[i ^ 1]) != 1) y -= vals[i ^ 1][1].F;
		}
		else{
			y -= vals[i ^ 1][0].F;
		}
		ans = min(ans, x + y); 
	}
	cout << ans;
} 
int main()
{
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
    Red;
  	int T = 1;
  	// cin >> T;
  	for(int i = 1; i <= T; ++i){
  		solve();
  	}
  	return 0;

}


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

int main() {
  int a;
  cin >> a;
  if(a == 0){
    cout << 0 << endl;
  }
  else if(a==1 || a==10 || a==100){
    cout << 1 << endl;
  }
  else if(a==11 || a==101 || a==110){
    cout << 2 << endl;
  }
  else{
    cout << 3 << endl;
  }
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

#define MOD 1000000007

int main()
{
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	char a[515][512] = {0};
	for(int i=0; i<n; ++i)
		cin >> &a[i][0];

	int ny[512] = {0};
	int nx[512] = {0};
	int nb = 0;
	for(int y=0; y<n; ++y)
		for(int x=0; x<n; ++x)
		{
			if(a[y][x] == '#')
			{
				++ny[x];
				++nx[y];
				++nb;
			}
		}
	
	if(nb == 0)
	{
		cout << "-1\n";
		return 0;
	}
	
	int ans = 999999;
	for(int y=0; y<n; ++y)
	{
		if(ny[y] == 0 && nx[y] == 0)
			continue;

		int v = 0;
		if(ny[y] == 0)
			v++;
		v += n-nx[y];
		ans = min(ans, v);
	}
	
	if(ans == 999999)
		*(int*)0=0;

	for(int x=0; x<n; ++x)
		if(ny[x] != n)
			ans += 1;
		
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 512
// url: http://abc075.contest.atcoder.jp/tasks/abc075_d

import std.algorithm, std.conv, std.range, std.stdio, std.string;

void main()
{
  auto rd1 = readln.split.to!(int[]), n = rd1[0], k = rd1[1];
  auto x = new int[](n), y = new int[](n);
  foreach (i; 0..n) {
    auto rd2 = readln.split.to!(int[]);
    x[i] = rd2[0];
    y[i] = rd2[1];
  }

  auto xd = x.dup, ix = 0;
  xd.sort();
  auto xs = xd.uniq.array;
  
  auto yd = y.dup, iy = 0;
  yd.sort();
  auto ys = yd.uniq.array;
  

  auto nx = xs.length, ny = ys.length, ans = long.max;

  foreach (nx1; 0..nx-1)
    foreach (nx2; nx1+1..nx)
      foreach (ny1; 0..ny-1)
        foreach (ny2; ny1+1..ny) {
          auto c = 0;
          foreach (i; 0..n)
            if (x[i] >= xs[nx1] && x[i] <= xs[nx2] && y[i] >= ys[ny1] && y[i] <= ys[ny2])
              ++c;
          if (c == k) ans = min(ans, long(xs[nx2] - xs[nx1]) * long(ys[ny2] - ys[ny1]));
        }

  writeln(ans);
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Contest
{
    class Program
    {
        static int Main(string[] args)
        {
            new Program().Process();

            return 0;
        }

        private CommonInput cin;

        private void Process()
        {
            this.cin = new CommonInput();

            int x, y;

            string s;

            while (true)
            {
                s = cin.GetLine();

                if (s == null)
                    break;

                x = int.Parse(s);
                y = cin.GetInt();

                Console.WriteLine("{0} {1}", this.Gcd(x, y), this.Lcm(x, y));
            }
        }

        private long Gcd(int x, int y)
        {
            if (y == 0)
                return x;
            else
                return this.Gcd(y, x % y);
        }

        private long Lcm(int x, int y)
        {
            return (long)x * y / this.Gcd(x, y);
        }
    }

    public class CommonInput
    {
        public CommonInput()
        {
            this._s = new string[0];
            this._i = 0;
        }

        private string[] _s;
        private int _i;
        private char[] _sep = { ' ' };

        public string GetLine()
        {
            if (this._i < this._s.Length)
                return this._s[this._i++];

            string line;
            this._i = 0;
            do
            {
                line = Console.ReadLine();
            } while (line == "");

            if (line == null)
                return null;

            this._s = line.Split(this._sep, StringSplitOptions.RemoveEmptyEntries);

            return this._s[this._i++];
        }

        public int GetInt()
        {
            return int.Parse(this.GetLine());
        }

        public long GetLong()
        {
            return long.Parse(this.GetLine());
        }

        public double GetDouble()
        {
            return double.Parse(this.GetLine());
        }
    }
}

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

#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); ++(i))
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); --(i))

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using int32 = int;
using int64 = long long;

const int   mod   = 1e9 + 7;
const int32 inf   = 1001001001;
const int64 infll = 1001001001001001001ll;

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

struct IoSetup { IoSetup(int x = 10){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = int64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } 
template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (T &in : v) is >> in; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p) { os << p.first << " " << p.second; return os; }
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }

template <typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

void solver() {
  auto digit_sum = [&](int64 a) {
    int res = 0;
    while (a) {
      res += a % 10;
      a /= 10;
    }
    return res;
  };

  int64 K = input();

  int64 ans = 1;
  range(i, 0, K) {
    cout << ans << endl;

    ans++;

    int64 k = 1, res = ans;
    range(d, 0, 17) {
      int64 x = k * (ans / k + 1) - 1;

      if (res * digit_sum(x) > x * digit_sum(res)) {
        res = x;
      }

      k *= 10;
    }

    ans = res;
  }
}

signed main(int argc, char *argv[]) {
  solver();
}


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


int main() {
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int count = 0;
    rep(i, a+1) rep(j, b+1) rep(k, c+1) {
        if (i * 500 + j * 100 + k * 50 == x) count++;
    }
    cout << count << endl;
    return 0;
}

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

int main(){
    int N,M;
    cin>>N>>M;
    vector<int> B(M,0);
    for(int i=0;i<N;i++){
        int K; cin>>K;
        for(int j=0;j<K;j++){
            int A; cin>>A; A--;
            B[A]++;
        }
    }

    int ans=0;
    for(int i=0;i<M;i++){
        if(B[i]==N) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 384
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,m = iim()
if 2*n > m:
    print(m//2)
else:
    print(n+(m-2*n)//4)

Measured memory_bytes: 3064
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    p = list(map(int, input().rstrip('\n').split()))
    sp = sorted(p)
    cnt = 0
    for i in range(n):
        if sp[i] != p[i]:
            cnt += 1
    print("YES" if cnt <= 2 else "NO")


if __name__ == '__main__':
    slove()


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

/**
 *  Name: Chris M. Perez
 *  University: Interamerican University Metro Campus
 *
**/

#define endl '\n'
#define MOD 10e18
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define gcd(x , y) __gcd(x , y)
#define all(x) (x).begin() , (x).end()
#define forn(i , a , b) for(int i=(a);i<(b);i++)
#define forrange(j , a , b) for(int j=(a);j<=(b);j++)
#define nestedforn(i , a , b , j , c , d) for(int i=(a);i<=(b);i++) for(int j=(c);j<=(d);j++)
#define sort_all(x) sort(all(x))
#define zeros_at_beginning(x) __builtin_clz(x)
#define zeros_at_end(x) __builtin_ctz(x)
#define ones(x) __builtin_popcount(x)
#define parity_even_or_odd_ones __builtin_parity(x)

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef tuple<int , int , int> tiii;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef long long int lli;

template< typename T1, typename T2 > struct pair {
  T1 first;
  T2 second;
};
               
inline int input(){
  int n;
  scanf("%d" , &n);
  return n;
}
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;

#ifdef LOCAL_DEFINE
  freopen("input.txt" , "rt" , stdin);
#endif
  
  string s; cin >> s;
  int size = s.length();
  if(size % 2 == 0) cout << s << endl;
  else {
    reverse(all(s));
    cout << s << endl;
  }
      
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif  
  return 0;
}

Measured memory_bytes: 256
#include <cmath>
#include <chrono>
#include <random>
#include <ctime>
#include <algorithm>
#include <iosfwd>
#include <iostream>
#include <list>
#include <ostream>
#include <streambuf>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef long long int ll;
typedef long long int ull;
typedef long double ld;
#define fori(i, n) for(ll i = 0; i < (n); ++i)
#define forI(i, n) for(ll i = 1; i <= (n); ++i)
#define pll pair<ll, ll>
#define ff first
#define ss second

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#define pt pair<ll, ll>
#define x first
#define y second

pll operator+(pll a, pll b) { return {a.x + b.x, a.y + b.y}; }
pll operator-(pll a, pll b) { return {a.x - b.x, a.y - b.y}; }

ll rand0m() {return (ull(rand()) << 15ull | ull(rand()));}                   //[0 ... n)
ll rand0m(ll x) {return rand0m() % x;}               //[0 ... n)
ll rand0m(ll minn, ll maxx) {return rand0m(maxx - minn + 1) + minn;}   //[minn ... maxx]

const ll MAXN = 100000 + 1;
const ll mod = 1e9 + 7;
const ll INF = 1e18;

ll n, m;

ll dp[1 << 16];
ll a[16][16];
ll v[16];
ll sm[1 << 16];
ll v_it = 0;

void solve(){
    cin >> n;
    fori(i, n) fori(j, n) cin >> a[i][j];
    fori(m, 1 << n){
        v_it = 0;
        fori(i, n) if(m >> i & 1) v[v_it++] = i;
        fori(i, v_it) fori(j, i) sm[m] += a[v[i]][v[j]];
    }
    fori(mask, 1 << n){
        for(ll d = mask; ; d = (d - 1) & mask){

            dp[mask] = max(dp[mask], dp[mask ^ d] + sm[d]);
            if(d == 0) break;
        }
    }
    cout << dp[(1 << n) - 1];
}

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

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //stress();
    solve();
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
const ll MX = 1e18;
 
int main() {
  int n;
  cin >> n;
//   答えの変数をデフォルト1で設定
  ll ans = 1;
//   最初フラグはngでセット
  bool ng = false;
  rep(i,n) {
    ll a;
    cin >> a;
    if (a == 0) {
        // もしaが0なら0出力結果して抜ける
      cout << 0 << endl;
      return 0;
    }
    // オーバーフロー、10^18を超えるかチェック
    if (ng || __int128(ans)*a > MX) {
      ng = true;
    }
    ans *= a;
  }
//   ngがtrueなら-1
  if (ng) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}

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

const int mx =  302;
int N;

double dp[mx][mx][mx];

double getdp(int xx,int yy, int zz) {
    if(xx < 0 || yy < 0 || zz < 0)
        return 0.0;
    if(dp[xx][yy][zz] >= 0.0)
        return dp[xx][yy][zz];

    dp[xx][yy][zz] = 0.0;
    double mul_ = 1.0, add_ = 0.0;
    // already eaten
    if(xx + yy + zz < N){
        mul_ = 1.0 * N / (xx + yy + zz);
        add_ = 1.0 * (N - xx -yy - zz) / (xx + yy + zz);
        dp[xx][yy][zz] += add_;
    }

    dp[xx][yy][zz] += mul_* (getdp(xx-1,yy,zz) + 1) * xx / N;
    dp[xx][yy][zz] += mul_* (getdp(xx+1,yy-1,zz) + 1) * yy / N;
    dp[xx][yy][zz] += mul_* (getdp(xx, yy+1, zz-1) + 1) * zz / N;
//    printf("%d %d %d : %lf\n", xx, yy, zz, dp[xx][yy][zz]);
    return dp[xx][yy][zz];
}

int main(){
    scanf("%d",&N);
    int cnt1 = 0;
    int cnt2 = 0;
    int cnt3 = 0;

    for(int i = 0 ;i < N; ++i){
        int tmp;scanf("%d", &tmp);
        switch (tmp) {
            case 1: cnt1 ++;break;
            case 2: cnt2 ++;break;
            case 3: cnt3 ++;break;
            default: break;
        }
    }
    // init dp, must N;
    for(int i = 0 ;i <= N; ++i){
        for(int j = 0 ;j <= N ; ++j){
            for(int k = 0 ; k <= N ; ++k){

//                printf("%d %d %d",i,j,k);
//                puts("OK");

                dp[i][j][k] = -1.0;
            }
        }
    }
    dp[0][0][0] = 0.0;

    printf("%.10lf\n",getdp(cnt1,cnt2,cnt3));

    return 0;
}

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

#define mp make_pair
#define pb push_back

using namespace std;

int r, c, n, vis[123456];
pair<int, int> a[123456], b[123456];
vector<pair<int, int> > g;
stack<int> st;

bool bor(pair<int, int> p){
	return p.first == 0 || p.second == 0 || p.first == r || p.second == c;
}

void push(pair<int, int> p, int x){
	if (p.first == 0) g.pb(mp(p.second, x));
	else if (p.second == c) g.pb(mp(p.first + c, x));
	else if (p.first == r) g.pb(mp(r + 2 * c - p.second, x));
	else g.pb(mp(2 * (r + c) - p.first, x));
}

int main(){
//	freopen("input.inp", "r", stdin);
	scanf("%d%d%d",&r,&c,&n);
	for(int i = 1; i <= n; ++i){
		scanf("%d%d%d%d",&a[i].first,&a[i].second,&b[i].first,&b[i].second);
		if (bor(a[i]) && bor(b[i])){
			push(a[i], i);
			push(b[i], i);
		}
	}
	sort(g.begin(), g.end());
	for(int i = 0; i < g.size(); ++i){
		int x = g[i].second;
		if (!vis[x]) vis[x] = 1, st.push(x);
		else{
			if (st.top() != x){
				printf("NO");
				return 0;
			}
			st.pop();
		}
	}
	printf("YES");
	return 0;
}

Measured memory_bytes: 4468
#include <cstdio>
    using namespace std;
    bool memo[100005];
    int main(){
        memo[0]=true;
        for (int x=100;x<=105;x++){
            for (int y=x;y<100005;y++){
                memo[y]|=memo[y-x];
            }
        }
        
        int n;
        scanf("%d",&n);
        printf("%d\n",memo[n]);
    }

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

using namespace std;

typedef long long ll;

#define INF (int)1e9+7
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
//#define N 100005
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626433832795
#define ld long double

ll powM(ll a,ll b,ll m )
{ 
  a%=m;
  ll ans=1;
  while(b>0)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }

return ans;
}






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

ld a,b,h,m;
cin>>a>>b>>h>>m;

ld an=h*30-(5.5)*m;

an*=PI/180;

ld ans=sqrt(a*a+b*b-2*a*b*cos(an));


cout<<fixed<<setprecision(15)<<ans<<"\n";



return 0;

}

Measured memory_bytes: 4100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
 
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 (a>b) { a=b; return 1; } return 0; }
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)



int main(){
    int n;
    cin>>n;
    vector<vector<P>> g(n);
    rep(i,n-1){
        int u,v,w;
        cin>>u>>v>>w;
        --u;--v;
        g[u].push_back(P(v,(w%2)));
        g[v].push_back(P(u,(w%2)));
    }
    stack<int> st;
    int ans[n];
    memset(ans,-1,sizeof(ans));
    ans[0]=0;
    st.push(0);
    while(!st.empty()){
        int sttop=st.top();
        st.pop();
        for(auto au:g[sttop]){
            if(ans[au.first]!=-1)continue;
            if(au.second==1){
                ans[au.first]=1-ans[sttop];
            }
            else ans[au.first]=ans[sttop];
            st.push(au.first);
        }
    }
    rep(i,n)cout<<ans[i]<<endl;
}

Measured memory_bytes: 6784
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <functional>
#include <set>
#include <numeric>
#include <queue>
#include<map>
#define ll long long int
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
#define PI 3.14159265358979323846264338327950


int main() {
	ll N, ans = 0;

	cin >> N;


	if (N == 0){
		cout << 1 << endl;
	}
	else{
		cout << 0 << endl;
	}
	return 0;
}

Measured memory_bytes: 3484
#include<bits/stdc++.h>
using namespace std;
char a[100005];
int x=0,y=0,ans=0;
int main()
{
    cin>>a;
    for (int i=0;i<sizeof(a);i++)
     if (x==y) {
         x++;
         if(a[i]=='p')ans--;
     }
     else {
         y++;
         if(a[i]=='g')ans++;
     }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main (void) {
  int  i, m[50], f[50], r[50], point;
  for ( i = 0; i < 50 ; i++ ){
    scanf("%d %d %d\n", m + i, f + i, r + i);
    if (*(m + i) < 0 && *(f + i) < 0 && *(r + i) < 0) break;
    point = *(m + i) + *(f + i);
    if ( *(m + i) < 0 || *(f + i) < 0) printf("F\n");
    else if ( 80 <= point ) printf("A\n");
    else if ( 65 <= point ) printf("B\n");
    else if ( 50 <= point ) printf("C\n");
    else if ( 30 <= point ) {
      if (50 <= *(r + i)) printf("C\n");
      else printf("D\n");
    }
    else printf("F\n");
  }
  return 0;
}


Measured memory_bytes: 2052
// テ・ツ淞コテヲツ慊ャテ」ツδ?」ツδウテ」ツδ療」ツδャテ」ツδシテ」ツδ?

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

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

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

const int S = 51;
// ax, ay, bx, by
bool visited[S][S][S][S];
int W, H;

struct Elem {
    int ax, ay, bx, by;
};

pii search_p(const vector<string> &vs, char target) {
    rep(i,0,H) rep(j,0,W) {
        if(vs[i][j] == target) return make_pair(i, j);
    }
    return make_pair(-1, -1);
}

void move_p(const vector<string> &vs, int &x, int &y, int dir, int mode) {
    int nx = max(0LL, min(H-1, x + dx[dir]));
    int ny = max(0LL, min(W-1, y + dy[dir] * mode));
    if(vs[nx][ny] == '#') return;
    x = nx;
    y = ny;
}

signed main() {
    while(cin >> W >> H, W || H) {
        memset(visited, false, sizeof(visited));

        vector<string> lboard(H), rboard(H);
        rep(i,0,H) cin >> lboard[i] >> rboard[i];
        pii init_a = search_p(lboard, 'L');
        pii init_b = search_p(rboard, 'R');
        int a = init_a.first, b = init_a.second;
        int x = init_b.first, y = init_b.second;

        pii goal_a = search_p(lboard, '%');
        pii goal_b = search_p(rboard, '%');
        int A = goal_a.first, B = goal_a.second;
        int X = goal_b.first, Y = goal_b.second;

        queue<Elem> que;
        que.push(Elem{a, b, x, y});
        visited[a][b][x][y] = true;
        while(!que.empty()) {
            Elem cur = que.front(); que.pop();
            rep(k,0,4) {
                Elem nxt = cur;
                move_p(lboard, nxt.ax, nxt.ay, k, -1);
                move_p(rboard, nxt.bx, nxt.by, k, 1);
                if(visited[nxt.ax][nxt.ay][nxt.bx][nxt.by]) continue;
                bool p = make_pair(nxt.ax, nxt.ay) == goal_a;
                bool q = make_pair(nxt.bx, nxt.by) == goal_b;
                if(p ^ q) continue;
                visited[nxt.ax][nxt.ay][nxt.bx][nxt.by] = true;
                que.push(nxt);
            }
        }

        if(!visited[A][B][X][Y]) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 11372
#include<bits/stdc++.h>
using namespace std;
bool a[110];
int main(){
  long long N,K,i,j;
  cin>>N>>K;
  
  for(i=0;i<K;i++){
long long d;
cin>>d;
for(j=0;j<d;j++){
    long long A;
    cin>>A;
    a[A]=true;
}
  }
  long long count=0;
  for(i=1;i<=N;i++){
      if(a[i]){
          count++;
      }

  }
  cout<<N-count<<endl;
  return 0;

  


}

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

int main(){
    int x,y;
    cin >> x >> y;
    int crane;
    crane = x*2;
    if(y%2 == 1 || crane > y || y > x*4){
        cout << "No" << endl;
        return 0;
    }
    int temp;
    temp = y - crane;
    int turtle;
    turtle = temp/2;
    crane = x - turtle;
    if(turtle >= 0 && crane >= 0){
        cout << "Yes" << endl;
        return 0;
    }else{
        cout << "No" << endl;
    }

}

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

using namespace std;
typedef long long ll;
int main() {
    ll i, n, k,m;
    priority_queue<ll> pq;
    cin >> n >> m;
    for(i = 0; i < n;i++){
        ll x;
        cin >> x;
        pq.push(x);
    }
    for(i = 0; i < m;i++){
        ll x=pq.top();
        pq.pop();
        pq.push(x / 2);
    }
    ll ret = 0;
    while(!pq.empty()){
        ret += pq.top();
        pq.pop();
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cout << H << " "; debug_out(T...); }
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n, a;
  cin >> n >> a;
  int ans = n*n - a;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void)
{
    int x1, y1, x2, y2, x3, y3, x4, y4;

    cin >> x1 >> y1 >> x2 >> y2;

    x3 = x2 - (y2 - y1);
    y3 = y2 + (x2 - x1);
    x4 = x3 - (x2 - x1);
    y4 = y3 - (y2 - y1);

    cout << x3 << ' ' << y3 << ' ' <<  x4 << ' ' <<  y4 << ' ' <<  endl;
    return 0;
}

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

ans = [float('inf')] * N
ans[0] =0
ans[1] = abs(ls[1]-ls[0])
for i in range(2, N):
    ans[i] = min(ans[i-1]+ abs(ls[i]-ls[i-1]), ans[i-2]+ abs(ls[i]-ls[i-2]))

print(ans[-1])

Measured memory_bytes: 20652