akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cerr<<*i<<" "; cerr<<endl; }
inline bool valid(int x, int y, int W, int H){ return (x >= 0 && y >= 0 && x < W && y < H); }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
void next(int& y, int& m, int &d){
  int end = 20;
  if(y % 3 != 0 && m % 2 == 0) end = 19;
  d++;
  if(d > end){
    d = 1;
    m++;
    if(m > 10){
      m = 1;
      y++;
    }
  }
}
int main(){
  int N;
  cin >> N;
  while(N --){
    int y, m, d;
    cin >> y >> m >> d;
    int ans = 0;
    while(y != 1000){
      ans++;
      next(y, m, d);
    }
    cout << ans << endl;
  }
  return 0;
}

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

vector<pair<long long,long long>> factor(long long x) {
   vector<pair<long long,long long>> ans;
   for (long long i = 2; i*i <= x; i++) {
      if(x % i == 0) {
         ans.push_back({i, 1});
         while ((x /= i) % i == 0) ans.back().second++;
      }
   }
   if(x != 1) ans.push_back({x, 1});
   return ans;
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);
   long long n;
   cin >> n;
   int ans = 0;
   for (auto [a,m]:factor(n)) {
      int M = m;
      for (int i = 1; i <= 100; i++) {
         if (M >= i) {
            M -= i;
            ans++;
         }
      }
   }   
   cout << ans << '\n';
   return 0;
}

Measured memory_bytes: 3612
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::*,
    std::{cmp::*, collections::*, convert::*, iter::*, marker::*, mem::*, ops::*},
};
fn main() {
    input! {//
        a:f64,b:f64,h:f64,m:f64,
    }
    let hh = PI * h / 6. + PI * m / 30. / 12.;
    let mm = PI * m / 30.;
    let nn = a * a + b * b - 2. * a * b * (hh - mm).cos();
    println!("{}", nn.sqrt());
}

const PI: f64 = 3.141592653589793;


Measured memory_bytes: 2992
import java.util.*;
public class Main {
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	int n=sc.nextInt();
    	int a=n%60;
    	n/=60;
    	int b=n%60;
    	n/=60;
    	
    	
    	System.out.println(n+":"+b+":"+a);
    }
}



Measured memory_bytes: 26184
import java.util.Scanner;

/**
 * @author yoshizaki
 *
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner= new Scanner(System.in);
        String s = scanner.next();
        StringBuilder sb = new StringBuilder();
        String ans = "Yes";
        int len = s.length();
        sb.append(s);
        if(!(sb.toString().equals(sb.reverse().toString()))) ans = "No";
        
        sb = new StringBuilder();
        sb.append(s.substring(0, ((len - 1) / 2)));
        if(!(sb.toString().equals(sb.reverse().toString()))) ans = "No";
        
        sb = new StringBuilder();
        sb.append(s.substring(((len + 3) / 2)-1, len));
        if(!(sb.toString().equals(sb.reverse().toString()))) ans = "No";
        
        System.out.println(ans);
    }
}

Measured memory_bytes: 23636
n=int(input())
a=list(map(int,input().split()))
q=int(input())
sum=sum(a)

count=[0]*(10**5+1)

for i in a:
    count[i]+=1

for i in range(q):
    b,c=map(int,input().split())
    if count[b]!=0:
        sum+=(c-b)*count[b]
        count[c]+=count[b]
        count[b]=0
    print(sum)

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

void trace(vector<int> &A, int N) {
  int i;
  for ( i = 0; i < N; i++ ) {
    if ( i > 0 ) cout << " ";
    cout << A.at(i);
  }
  cout << endl;
}

void insertionSort(vector<int> &A, int N) {
  int j, i, v;
  for ( i = 1; i < N; i++ ) {
    v = A.at(i);
    j = i - 1;
    while ( j >= 0 && A.at(j) > v) {
      A.at(j+1) = A.at(j);
      j--;
    }
    A.at(j+1) = v;
    trace(A, N);
  }
}

int main() {
  int N, i, j;
  cin >> N;
  vector<int> A(N);
  for ( i = 0; i < N; i++ ) cin >> A.at(i);

  trace(A, N);
  insertionSort(A, N);

  return 0;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
int n,m,pa1[12],pa2[12];
string grid[12],sorg[12];
char buf[12];
bool ac(int id1,int id2){
	for(int it=0;it<n;it++) if(grid[it][id1]!=grid[pa1[it]][id2]) return false;
	return true;
}
void dfs1(int cur,int rem){
	if(cur==m) cout<<"YES"<<endl,exit(0);
	else if(pa2[cur]!=-1) dfs1(cur+1,rem);
	else{
		for(int nxt=cur+1;nxt<m;nxt++)
			if(pa2[nxt]==-1&&ac(cur,nxt))
				pa2[nxt]=cur,pa2[cur]=nxt,dfs1(cur+1,rem),pa2[nxt]=pa2[cur]=-1;
		if(rem) pa2[cur]=cur,dfs1(cur+1,0),pa2[cur]=-1;
	}
}
void dfs2(int cur,int rem){
	if(cur==n) dfs1(0,(m%2));
	else if(pa1[cur]!=-1) dfs2(cur+1,rem);
	else{
		for(int nxt=cur+1;nxt<n;nxt++)
			if(pa1[nxt]==-1&&sorg[cur]==sorg[nxt])
				pa1[nxt]=cur,pa1[cur]=nxt,dfs2(cur+1,rem),pa1[nxt]=pa1[cur]=-1;
		if(rem) pa1[cur]=cur,dfs2(cur+1,0),pa1[cur]=-1;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	memset(pa1,-1,sizeof(pa1));
	memset(pa2,-1,sizeof(pa2));
	for(int i=0;i<n;i++) scanf("%s",buf),grid[i]=buf;
	for(int i=0;i<n;i++) sorg[i]=grid[i],sort(sorg[i].begin(),sorg[i].end());
	dfs2(0,(n%2));
	cout<<"NO"<<endl;
	return 0;
}


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

int main(void) {
    int N;
    int A;
    int B;
    int C;
    int X;
    int next_X;
    int Y;
    int next_Y;
    int flame_num;

    std::cin >> N;
    while (N != 0) {
        Y = -2;
        flame_num = 0;
        std::cin >> A >> B >> C >> X;
        for (int i = 0; i < N; i++) {
            std::cin >> next_Y;
            if (next_Y == Y) {
                flame_num++;
                next_X = (A * X + B) % C;
                X = next_X;
            }
            Y = next_Y;
            while (Y != X) {
                flame_num++;
                next_X = (A * X + B) % C;
                X = next_X;
                if (flame_num > 10000) {
                    break;
                }
            }
        }

        if (flame_num > 10000) {
            std::cout << "-1" << std::endl;
        }

        if (flame_num <= 10000) {
            std::cout << flame_num << std::endl;
        }
        std::cin >> N;
    }

    return EXIT_SUCCESS;
}

Measured memory_bytes: 3088
import bisect
import sys
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7
#DIV = 998244353

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():
    cache={"0":0}
    def get_pc(s):
        pc = sum([c == '1' for c in s])
        return pc

    def modPC(s,pc=None):
        if pc==None:
            pc =get_pc(s)
        return int(s,2)%pc

    def f(s,cur=0):
        if s in cache:
            return cache[s]
        next_s = bin(modPC(s))[2:]
        ret = f(next_s,cur+1)+1
        cache[s]=ret
        return ret
    N=iRaw()
    Xs=sRaw()
    XPC = get_pc(Xs)
    XmodPC=None
    if XPC!=0:
        XmodPC = modPC(Xs,XPC)
    XmodPCP = modPC(Xs,XPC+1)
    XmodPCN = None
    if XPC>1:
        XmodPCN= modPC(Xs,XPC-1)

    for n in range(N):
        if Xs[n]=='1':
            if XPC==1:
                print(0)
            else:
                nxt=(XmodPCN-pow(2,N-n-1,XPC-1))%(XPC-1)
                nxt = bin(nxt)[2:]
                print(f(nxt)+1)
        else:
            nxt = (XmodPCP+pow(2, N-n-1, XPC+1)) % (XPC+1)
            nxt = bin(nxt)[2:]
            print(f(nxt)+1)

main()


Measured memory_bytes: 88176
#include <cstdio>
#include <iostream>

using namespace std;

bool is_prime(const unsigned n);


int main(){
	int n;

	while(cin >> n){
		int ans=0;

		for(int number=2;number<=n;number++){
			if(is_prime(number))ans++;
		}
		printf("%d\n",ans);
	}


	return 0;
}

bool is_prime(const unsigned n){
    switch(n){
        case 0: 
        case 1: return false;
        case 2: 
        case 3: return true;
    } 

    if(n%2 == 0) return false;
    if(n%3 == 0) return false;

    if(n%6 != 1 && n%6 != 5) return false;

    for(unsigned i=5;i*i<=n;i+=6){
        if(n%i     == 0) return false;
        if(n%(i+2) == 0) return false;
    }

    return true;}

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

const int dy[] = {1,0,-1,0}, dx[] = {0,1,0,-1};
const string news = "NESW";

int main(){
  int n,x0,y0,t;
  bool g[51][51][4] = {};
  cin >> n >> x0 >> y0 >> t;

  while(n--){
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int dify = y2-y1, difx = x2-x1;
    if(dify)dify /= abs(y2-y1); if(difx)difx /= abs(x2-x1);

    rep(d,4){
      if(dy[d] == dify && dx[d] == difx){
	int cy = y1, cx = x1;
	while(cy!=y2 || cx!=x2){
	  g[cy][cx][d] = 1;
	  cy += dy[d]; cx += dx[d];
	  g[cy][cx][(d+2)%4] = 1;
	}
      }
    }
  }

  int cur[51][51][4], nxt[51][51][4];
  memset(cur,0,sizeof(cur));
  rep(d,4)cur[y0][x0][d] = 1;

  while(t--){
    int dis; char dir;
    cin >> dis >> dir;
    while(dis--){
      memset(nxt,0,sizeof(nxt));

      rep(i,51)rep(j,51)rep(d,4){
	if(cur[i][j][d]==2){
	  for(int k=-1;k<=1;k++){
	    int nd = (d+k+4)%4, ny = i+dy[nd], nx = j+dx[nd];
	    if(g[i][j][nd])nxt[ny][nx][nd] = 2;
	  }
	}else if(cur[i][j][d]==1){
	  int ny = i+dy[d], nx = j+dx[d];
	  if(g[i][j][d])nxt[ny][nx][d] = 2;
	}
      }

      swap(cur,nxt);
    }

    memset(nxt,0,sizeof(nxt));
    
    rep(i,51)rep(j,51)rep(d,4){
      if(cur[i][j][d]){
	if(news[d]==dir)nxt[i][j][d] = 2;
	else{
	  for(int k=-1;k<=1;k++){
	    int nd = (d+k+4)%4;
	    if(g[i][j][nd] && news[nd]==dir)nxt[i][j][nd] = max(nxt[i][j][nd],1);
	  }
	}
      }
    }
    swap(cur,nxt);
  }

  rep(x,51)rep(y,51){
    bool f = false;
    rep(d,4)f |= cur[y][x][d]>0;
    if(f)cout << x << " " << y << endl;
  }
}

Measured memory_bytes: 1308
#include <iostream>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    if(n&1)
    cout << "No" << endl;
    else
    {
        int f=0;
        for(int i=0;i<n/2;i++)
        {
            if(s[i]!=s[i+n/2])
            f=1;
            //cout << s[i] << " " << s[i+n/2] << endl;
        }
        if(f==0)
        cout << "Yes" << endl;
        else
        cout << "No" << endl;
    }
    return 0;
}

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

#define pb push_back
#define rb  pop_back
#define rf  pop_front
#define ins insert
#define f   first
#define s   second
#define um  unordered_map
#define us  unordered_set
#define pq  priority_queue

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
typedef pair< long long int ,long long int > iil;
typedef long long ll;
typedef unsigned long long ull;
typedef vector< ll > vl;
typedef vector< vl > vvl;
typedef vector<double> vd;
typedef pair<double,double> pd;
typedef queue<int> qi;
typedef queue<double> qd;
typedef queue<ll> qll;
typedef us<int> si;
typedef us<double> sd;
typedef us<ll> sll;
typedef vector<vd> md;


const int MAX = 1e6;
const int N = 200043;
const int MOD = 998244353;

#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define sz(a) int((a).size())
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for( auto i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define EE endl
#define PI 3.14159265
#define g(a,b) a>b?a:b
#define l(a,b) a<b?a:b
#define SOT(A) sort(A.begin(),A.end())
#define SOTR(A) sort(A.rbegin(),A.rend())
#define REV(a) reverse(ALL(a))

// LOOP Control Statements
#define forn(i,j,n) for ( auto i=j ; i<n ; i++ )
#define fornd(i,j,n) for ( auto i=j ; i>n ; i-- )
#define FORE(i, b) for(auto &i:b)


#define SQ(i) (i*i)
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define IN(a, b) (a.find(b) != a.end())
#define BACK(a) a.back(); a.RB()
#define QBACK(a) a.top(); a.pop()
#define PRINT(a) FORE(i, a) cout << i << " "; cout << endl

#define tcase(term) int tc;cin>>tc;for(int term=0; cout<<"CASE "<<term+1<<EE,term<tc;term++)

vector<bool> is_prime(MAX+1, true);
void Sieve(){
	is_prime[0] = is_prime[1] = false;
	ll i,j;
	for (i = 2; i*i <= MAX; i++) {
    	if (is_prime[i]) {
        	for (j = i * i; j <= MAX; j += i)
            	is_prime[j] = false;
    	}
	}
}

int main()
{
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
 //    tcase(terms)
    {
		  int N;
		  cin >> N;
		  int m = 1000000000;
		  int mc = 0;
		  long long sum = 0;
		  for (int i = 0; i < N; i++) {
		    int x;
		    cin >> x;
		    if (x < 0) mc += 1;
		    sum += abs(x);
		    m = min(m,abs(x));
		  }
		  cout << (mc % 2 == 0 ? sum : sum - 2*m) << endl;

	}
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Main
{
    class Program
    {
        static void Main(string[] arg)
        {
            var line = Console.ReadLine().ToCharArray();
            string answer = "";
            foreach (char c in line)
            {
                string str = c == '1' ? "9" : "1";
                answer += str;
            }

            Console.WriteLine(answer);
            Console.ReadLine();

        }
    }
}


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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

using namespace std;

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

using ll = long long;
using ld = long double;

const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);

struct UnionFind {
  vector<int> p;
  UnionFind (int n) : p(n, -1) {}
  int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }
  void merge(int x, int y) { if (root(x) != root(y)) p[root(y)] = x; }
};

int main(){
  int n, m;
  cin >> n >> m;
  UnionFind res = UnionFind(n);
  int x, y, tmp;
  REP(i, m) { cin >> x >> y >> tmp; res.merge(--x, --y); }
  set<int> roots;
  REP(i, n) roots.insert(res.root(i));
  cout << roots.size() << endl;
  return 0;
}

Measured memory_bytes: 5376
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define LB(a,x) lb(all(a),x)-a.begin()
#define UB(a,x) ub(all(a),x)-a.begin()
#define mod 1000000007
//#define mod 998244353
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }
template<class T> inline void out(T a){ cout << a << '\n'; }
void YN(bool ok){if(ok) cout << "Yes" << endl; else cout << "No" << endl;}
//void YN(bool ok){if(ok) cout << "YES" << endl; else cout << "NO" << endl;}


const ll INF=1e18;
const int mx=200005;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    V<ll> a(n);
    rep(i,n){
        cin>>a[i];a[i]--;
    }
    set<ll> st;
    V<ll> b;
    ll pos=0;
    ll cnt=0;
    ll ans;
    while(true){
        if(cnt==0){
            st.insert(pos);
            b.pb(pos);
            cnt++;
        }else{
            if(st.count(pos)||cnt-1==k){
                if(cnt-1==k){
                    ans=b.back();
                    break;
                }
                int i;
                ll c=0;
                ll j;
                for(i=0;i<b.size();i++){
                    if(b[i]==pos){
                        j=i;
                        c=(ll)b.size()-i;
                        break;
                    }
                }
                k-=j-1;
                k=k-(k/c)*c;
                if(k==0) ans=b.back();
                else ans=b[j+k-1];
                break;
            }
            cnt++;
            st.insert(pos);
            b.pb(pos);
        }
        pos=a[pos];
    }
    out(ans+1);
}

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

#define      pb    push_back
#define      ff    first
#define      ss    second
#define      ll    long long int
#define      endl  "\n"
#define      FASTIO        ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define      TEST    ll t ; cin >> t ; while( t -- )


//------------------------------------------------------------------------//

#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sc4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)

//------------------------------------------------------------------------//

const ll big = 10e15 + 11 ;


int  main (  ) {

    FASTIO ;

    int n , k , d ;
    cin >> n >> k  ;

    set < int > s ;

    while( k-- ){
        cin >> d ;

        while( d-- ){
            int x ;
            cin >> x ;

            s.insert( x ) ;
        }
    }

    cout << n - s.size( ) ;


    return  0 ;
}


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

using namespace std;

int fib[50];

int main()
{

    int n;

    fib[0]=fib[1]=1;

    cin>>n;

    for(int i=2;i<=n;i++)
    {
        fib[i]=fib[i-1]+fib[i-2];
    }

    cout<<fib[n]<<endl;


    return 0;
}



Measured memory_bytes: 3112
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

void NG() {
  puts("No");
  exit(0);
}

bool check1(char *s, int a, int b){
  for(int i=a;i<b;i++){
    if(s[i] == '#' && s[i+1] == '#') return false;
  }
  return true;
}

bool check2(char *s, int a, int b){
  for(int i=a+1;i<b;i++){
    if(s[i-1] == '.' && s[i] == '.' && s[i+1] == '.')
      return true;
  }
  return false;
}

int main(){
  int N, A, B, C, D;
  char s[SIZE];

  scanf("%d%d%d%d%d", &N, &A, &B, &C, &D);
  scanf("%s", s);

  A--; B--; C--; D--;

  if(C < A) NG();
  if(D < B) NG();

  if (A > B) {
    swap(A, B);
    swap(C, D);
  }

  if(!check1(s, A+1, C-1)) NG();
  if(!check1(s, B+1, D-1)) NG();

  if (A < B && B < C) {
    bool ok = false;

    if(C < D){
      ok = true;
    }else{
      ok = check2(s, max(A, B-1), min(C, D+1));
    }

    if (!ok) NG();
  }

  puts("Yes");


  return 0;
}


Measured memory_bytes: 384
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=110,p=1e9+7;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
int n,k,prime[N],pw[N],cnt;
void factor(int x){
	for (int i=2;i*i<=x;i++)
	if (x%i==0){
		prime[++cnt]=i;
		while (x%i==0) pw[cnt]++,x/=i;
	}
	if (x>1) prime[++cnt]=x,pw[cnt]=1;
}
int ans,fac[1<<20],bit[1<<20],bits[1<<20];
void dfs(int x,int val){
	if (x>cnt){
        int size=0;
        for (int i=1;i<=cnt;i++)
            if (val%prime[i]==0) bit[1<<(size++)]=prime[i];
        fac[0]=1;
        for (int i=1;i<(1<<size);i++) fac[i]=fac[i^(i&-i)]*bit[i&-i];
        int calc=0;
        for (int i=0;i<(1<<size);i++){
            int v=power(k,(val/fac[i]+1)>>1);
            calc=(bits[i]&1?dec(calc,v):inc(calc,v));
        }
        if ((val&1)==0) val/=2;
        ans=inc(ans,mul(calc,val));
        return;
	}
	dfs(x+1,val);
	for (int i=1;i<=pw[x];i++) dfs(x+1,val*=prime[x]);
}
int main()
{
	scanf("%d%d",&n,&k);
	factor(n);
	for (int i=0;i<(1<<20);i++) bits[i]=bits[i>>1]+(i&1);
	dfs(1,1);
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 8320
import java.util.Scanner;
import java.util.Arrays;

public class Main {

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

    void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long ans = Long.MAX_VALUE;
        for (int i = 1; i <= N - 1; i++) {
            int A = N - i;
            ans = Math.min(ans, i / 10000 + i / 1000 % 10 + i / 100 % 10 + i / 10 % 10 + i % 10 + A / 10000 + A / 1000 % 10 + A / 100 % 10 + A / 10 % 10 + A % 10);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 25300
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
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;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
int main(){
    ll n,m;cin >> n >>m;
    if(m==n-1)cout << 0 <<endl,exit(0);
    if((n-m-1)*2>n)cout << "Impossible" <<endl,exit(0);
    vl a(n);rep(i,n)cin >> a[i];
    UnionFind uf(n);
    rep(i,m){
        ll x,y;cin >> x >>y;
        if(!uf.same(x,y))uf.merge(x,y);
    }
    map<ll,multiset<ll>> mp;
    rep(i,n){
        mp[uf.root(i)].ins(a[i]);
    }
    vl use;
    ll ans=0;
    for(auto p:mp){
      ll cnt=0;
      for(auto z:p.se){
        if(cnt==0)ans+=z;
        else use.pb(z);
        cnt++;
      }
    }
    sort(all(use));
    rep(i,n-m-2){
        ans+=use[i];
    }
    cout << ans <<endl;
}


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

#define INF 1234567890
#define ll long long

int T, N, K;
int arr[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> K;
	cout << arr[K-1];
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define md 1000000007
#define ll long long 
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fastmap mp.reserve(1024);mp.max_load_factor(0.25);
#define fastset st.reserve(1024);st.max_load_factor(0.25);
ll int mpw(ll int a,ll int b,ll int m)
{
	ll int ans=1;
	if(a==0)return 0;
	if(a==1 || b==0)return 1;
	while(b)
	{
		if(b&1)
		{
			ans=(ans*a)%m;
		}
		a=(a*a)%m;
		b>>=1;
	}
	return ans;
}
 
ll int pw(ll int a,ll int b)
{
	ll int ans=1;
	if(a==0)return 0;
	if(a==1 || b==0)return 1;
	while(b)
	{
		if(b&1)
		{
			ans*=a;
		}
		a*=a;
		b>>=1;
	}
	return ans;
}
 
ll int mn(ll int a,ll int b)
{
	if(a<=b)
	{
		return a;
	}
	return b;
}
 
ll int mx(ll int a,ll int b)
{
	if(a>=b)
	{
		return a;
	}
	return b;
}
 
int main()
{
	fio
	int n;
	cin>>n;
	vector<vector<int>>g(n);
	for(int i=0;i<n-1;++i)
	{
		int a,b;
		cin>>a>>b;
		g[a-1].push_back(b-1);
		g[b-1].push_back(a-1);
	}
	vector<bool>vis(n,false);
	vector<pair<ll int,ll int>>D(n,{0,0});
	std::function<void(int)>dfs=[&](int node)->void{
		int nm=0;
		vis[node]=true;
		ll int ans1=1,ans2=1;
		for(int i=0;i<g[node].size();++i)
		{
			if(!vis[g[node][i]])
			{
				nm++;
				dfs(g[node][i]);
				ans1=(ans1*((D[g[node][i]].first+D[g[node][i]].second)%md))%md;
				ans2=(ans2*D[g[node][i]].first)%md;
			}
		}
		if(nm==0)
		{
			D[node].first=1;
			D[node].second=1;
		}
		else{
			D[node].first=ans1;
			D[node].second=ans2;
		}
		return;
	};

	dfs(0);
	cout<<(D[0].first+D[0].second)%md<<"\n";
	return 0;
}

Measured memory_bytes: 18344
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

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

int main()
{
	int x,y;
	cin >> x >> y;
	cout << x + y/2 << endl;

	return 0;
}

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

using namespace std;
#define rep(i,n) for(int i = 0; i < (n); ++i)
const double EPS = 1e-8;
const double INF = 1e12;
#define pb push_back



int N,M,LL;
double d[128][128];

typedef complex<double> P;
bool operator < (const P& a, const P& b){
	return  real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}

double cross(const P& a, const P& b){
	return imag(conj(a)*b);
}

double dot(const P& a, const P& b){
	return real(conj(a)*b);
}

struct L : public vector<P>{
	L(){}
	L(const P &a, const P &b){
		push_back(a);
		push_back(b);
	}
};

typedef vector<P> G;
struct C {
	P p;double r;
	C(const P &p, double r) : p(p), r(r) {}
};

int ccw(P a, P b, P c){
	b -= a;c -=a;
	if( cross(b,c)>0)return +1;
	if(cross(b,c) < 0) return -1;
	if(dot(b,c) < 0) return +2;
	if(norm(b) < norm(c)) return -2;
}

bool intersectLL(const L& l, const L& m){
	return abs(cross(l[1]-l[0], m[1]-m[0])) > EPS || abs(cross(l[1]-l[0], m[0]-l[0])) < EPS;
}

bool intersectSS(const L&s, const L &t){
	return ccw(s[0], s[1], t[0])*ccw(s[0],s[1],t[1]) <= 0 && ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1])<=0;
}

bool intersectSP(const L &s, const P &p){
	return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS;
}

P projection(const L &l, const P &p){
	double t = dot(p-l[0], l[0]-l[1]) / norm(l[0]-l[1]);
	return l[0] + t*(l[0]-l[1]);
}

double distanceLP(const L &l, const P& p){
	return abs(p - projection(l,p));
}

double distanceLL(const L &l, const L &m){
	return intersectLL(l,m) ? 0 : distanceLP(l, m[0]);
}

double distanceSP(const L&s, const P &p){
	const P r = projection(s,p);
	if(intersectSP(s,r)) return abs(r-p);
	return min(abs(s[0]-p), abs(s[1]-p));
}

double distanceSS(const L &s, const L &t){
	if(intersectSS(s,t)) return 0;
	return min(min(distanceSP(s,t[0]), distanceSP(s,t[1])),min(distanceSP(t,s[0]), distanceSP(t,s[1])));
}

double tod(double r){
	return M_PI * r / 180;
}

struct star{
	P p[5];
	L l[5];
	star(double x, double y, double a, double r){
		double n = 72;
		a+=90;
		rep(i,5){
			p[i] = P(x+r*cos(tod(a+n*i)), y+r*sin(tod(a+n*i)));
		}
		l[0] = L(p[0],p[2]);
		l[1] = L(p[0],p[3]);
		l[2] = L(p[1],p[3]);
		l[3] = L(p[1],p[4]);
		l[4] = L(p[2],p[4]);
	}
};


void init(){
	rep(i, 128)rep(j,128)d[i][j] = INF;
	rep(i,128)d[i][i]=0;
}
	


int main() {
	while(1){
		cin >> N >> M >> LL;
		if( N == 0) break;
		int x,y,a,r;
		M--;
		LL--;
		init();
		vector<star> stars;

		rep(i,N){
			cin >> x >> y >> a >> r;
			stars.pb(star(x,y,a,r));
		}

		
		rep(i,N)rep(j,N){
			rep(k,5)rep(kk,5){
				d[i][j] = min(d[i][j], distanceSS(stars[i].l[k], stars[j].l[kk]));
				d[j][i] = d[i][j];
			}
		}


		rep(k,N)rep(i,N)rep(j,N){
			d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
		}

	//	rep(i,5)rep(j,5)cout << i << "-" << j << "->" << d[i][j] << endl;
		cout << fixed << setprecision(10);
		cout << d[M][LL] << endl;
	}

	return 0;
}

Measured memory_bytes: 1480
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)

int n;

int main()
{
    cin >> n;
    int x,y;
    x = n * 800;
    y = (n / 15);
    y *= 200;

    cout << x - y << endl;
}

Measured memory_bytes: 256
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
#start = time.clock()

n=int(raw_input())
for h in range(n):
    tmp=raw_input()
    for a in range(26):
        if gcd(a,26)!=1:
            continue
        for b in range(26):
            s=''
            for q in tmp:
                if q.isalpha():
                    s+=chr((((ord(q)-97)*a+b)%26)+97)
                else:
                    s+=q
            if 'that' in s or 'this' in s:
                print s

Measured memory_bytes: 6332
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << # x << "; "<< x << endl


int main() {
	long long A, B, K;
	cin >> A >> B >> K;
	if (K <= A) {
		cout << A - K << " "<< B << endl;
	}
	else if (A < K && K <= A + B) {
		cout << 0 << " " << A + B - K << endl;
	}
	else {
		cout << 0 << " " << 0 << endl;
	}
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using ll = long long;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<ll> VLL;
typedef vector<string> VS;

struct N {
  string suit;
  long value;
};
int n; vector<N> A(100000), B(100000);

int partition(int p, int r) {
  int x = A.at(r-1).value;
  int nn = r-p;
  int c = 0;
  rep(i, nn-1){
    if (A.at(p+i).value <= x) {
      swap(A.at(p+i), A.at(p+c));
      c++;
    }
  }
  swap(A.at(r-1), A.at(p+c));
  return p+c;
}

void quickSort(int p, int r) {
  if (p < r) {
    int q = partition(p, r);
    quickSort(p, q);
    quickSort(q+1, r);
  }
}

void merge(int l, int m, int r) {
  int n1 = m-l;
  int n2 = r-m;
  long INF= long(1e+9)+1;
  vector<N> L(n1+1);
  vector<N> R(n2+1);
  rep(i, n1) {
    L.at(i) = B.at(l+i);
  }
  rep(i, n2) {
    R.at(i) = B.at(m+i);
  }
  L.at(n1).value = INF;
  R.at(n2).value = INF;
  int lh, rh;
  lh = rh = 0;
  rep(i, n1+n2) {
    if (L.at(lh).value <= R.at(rh).value) {
      B.at(l+i) = L.at(lh);
      lh++;
    } else {
      B.at(l+i) = R.at(rh);
      rh++;
    }
  }
}

void mergeSort(int l, int r) {
  if (l+1 < r) {
    int mid = (l+r)/2;
    mergeSort(l, mid);
    mergeSort(mid, r);
    merge(l, mid, r);
  }
}

string checkStable() {
  rep(i, n) {
    if (A.at(i).suit != B.at(i).suit) {
      return "Not stable";
    }
  }
  return "Stable";
}

int main() {
  cin >> n;
  rep(i, n){
    cin >> A.at(i).suit;
    B.at(i).suit = A.at(i).suit;
    cin >> A.at(i).value;
    B.at(i).value = A.at(i).value;
  }
  quickSort(0, n);
  mergeSort(0, n);
  cout << checkStable() << endl;
  rep(i, n) {
    cout << A.at(i).suit << " " << A.at(i).value << endl;
  }
}



Measured memory_bytes: 12136
#include<bits/stdc++.h>
using namespace std;
int main(){
  int x=0,n;
    string s;
    cin>>n;
  s=to_string(n);
  for(int i=0;i<(int)s.size();i++){
      x+=s[i]-'0';
//It converts an int in char form into an actual int.For example, if s[i] is '9' then s[i] - '0' will produce 9.
    }
  if(n%x==0){
		cout<<"Yes"<<endl;
  }
  	else cout<<"No"<<endl;
}

Measured memory_bytes: 256
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

N,M,Q = map(int,input().split())
ABCD = [tuple(map(int,input().split())) for _ in range(Q)]

ans = 0
def dfs(before):
    global ans
    if len(before) == N:
        score = 0
        for a,b,c,d in ABCD:
            a -= 1
            b -= 1
            if before[b] - before[a] == c:
                score += d
        ans = max(ans,score)
        return
    for i in range(before[-1],M + 1):
        before.append(i)
        dfs(before)
        before.pop()

dfs([1])
print(ans)   

Measured memory_bytes: 9088
#include <iostream>

using namespace std;

int main()
{
	int i, n, count = 0;
	string s;

	cin >> s;
	n = s.size();
	for (i = 0; i < n/2; i++) {
		if (s[i] != s[n - 1 - i]) count++;
	}
	cout << count;

	return 0;
}

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

typedef pair<int,int> pii;

bool cmp(pii x, pii y){
  return x.second > y.second;
}

int main(){
  long N, M;
  cin >> N >> M;
  vector<long> A;

  for(int i = 0; i < N; i++){
    long x;
    cin >> x;
    A.push_back(x);
  }

  vector<pii> v;
  for(int i = 0; i < M; i++){
    long x,y;
    cin >> x >> y;
    v.push_back(make_pair(x,y));
  }

  // 全部書き換わったとしたら、N個
  // vから大きい順にN個とって、Aに足して、ソートして、上からN個取る
  //
  sort(v.begin(), v.end(), cmp);
  // cerr << v[0].first << "," << v[0].second << endl;

  int counter = 0;
  for(int i = 0; i < M; i++){
    if(counter >= N) break;
    for(int j = 0; j < v[i].first && counter < N; j++){
      A.push_back(v[i].second);
      counter++;
    }
  }

  sort(A.begin(), A.end(), greater<int>());
  
  long ans = 0;
  for(int i = 0; i < N; i++){
    ans += A[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 3316
#include<stdio.h>
int main() 
{
	long long n, m;
	scanf("%lld%lld", &n, &m);
	//if ((m - n * 2) % 4 == 0)
	if (2 * n <= m)
		printf("%lld\n", (m - n * 2) / 4 + n);
	else
		printf("%lld\n", m / 2);
	//else
	//{

	//}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
ll D;
ll c[26];
ll s[366][26];
ll t[366];
ll score(ll days){
	ll ans=0;
	ll last[26];
	rep(i,26)last[i]=0;
	for(ll d=1;d<=days;d++){
		ans+=s[d][t[d]];
		last[t[d]]=d;
		rep(i,26){
			ans-=c[i]*(d-last[i]);
		}
	}
	return ans;
}

ll whole_score;
ll score_typ[26];
void recalc(ll i){
	ll ans=0;
	ll last=0;
	for(ll d=1;d<=D;d++){
		if(t[d]==i){
			ans+=s[d][i];
			last=d;
		}
		ans-=c[i]*(d-last);
	}
	whole_score-=score_typ[i];
	score_typ[i]=ans;
	whole_score+=score_typ[i];
}
void init_score(){
	whole_score=0;
	rep(i,26){
		score_typ[i]=0;
		recalc(i);
	}
}

int main(){
	cin>>D;
	rep(i,26)cin>>c[i];
	for(ll d=1;d<=D;d++)rep(j,26)cin>>s[d][j];
	for(ll d=1;d<=D;d++){
		cin>>t[d];
		t[d]--;
	}
	init_score();
	ll m;
	cin>>m;
	while(m--){
		ll d,q;
		cin>>d>>q;
		q--;
		ll b=t[d];
		t[d]=q;
		recalc(b);
		recalc(q);
		cout<<whole_score<<"\n";
	}
	/*for(ll d=1;d<=D;d++){
		ll ma=-1e17,pt=0;
		rep(i,26){
			t[d]=i;
			ll res=score(d);
			if(ma<res){
				ma=res;
				pt=i;
			}
		}
		t[d]=pt;
	}
	for(ll d=1;d<=D;d++){
		cout<<t[d]+1<<"\n";
	}*/
}


Measured memory_bytes: 3692
#include<bits/stdc++.h>
#define LIM 1+2+4+8+16+32+64+128
using namespace std;
typedef long long int ll;
int main(){
  ll n,d;
  cin>>n>>d;
  if(d-n>2020){
    cout<<0<<endl;
  }else{
    ll min;
    min=((n%2019)*((n+1)%2019))%2019;
    if(min!=0){
      for(ll i=n;i<=d;i++){
	for(ll j=i+1;j<=d;j++){
	  if(min>((i%2019)*(j%2019))%2019){
	    min=((i%2019)*(j%2019))%2019;
	    if(min==0){
	      break;
	    }
	  }
	}
	if(min==0){
	  break;
	}
      }
    }
    cout<<min<<endl;
  }
  return(0);
}


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

typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define ALL(a) begin(a),end(a)
template<class T> inline void sort_uniq(T& c) { sort(ALL(c)); c.erase(unique(ALL(c)), c.end()); }
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_v(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << endl; }
template<class K, class V> void cout_v(map<K, V>& m)
{ for(auto it=m.begin();it!=m.end();it++)cout<<it->first<<":"<<it->second<<endl;}
template<class T> void cout_h(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
inline int powi(int x,int y) {int p=1; while(y--) p*=x; return p;}
template<class T> inline bool is_overlap(const T& a, const T& b, const T& p, const T& q)
{ return p <=b && a <= q; }
#define MOD = 1000000007;
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
#define ANS(a) cout<<a<<endl
void yes(bool f){cout<<(f?"yes":"no")<<endl;}
void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
void YES(bool f){cout<<(f?"YES":"NO")<<endl;}

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    int A,B,C,D,E,F; cin >>A>>B>>C>>D>>E>>F;

    double max_density = -DBL_MIN;
    double saturated = E / (E + 100.0);
    int memo[2] = {0, 0};
    for (int a = 0; a <= F/(100*A); a++) {
        for (int b = 0; b <= F/(100*B); b++) {
            if (a == 0 && b == 0) continue;
            for (int c = 0; c <= F/C; c++) {
                for (int d = 0; d <= F/D; d++) {
                    int m = 100*A*a+100*B*b+C*c+D*d;
                    int m_salt = C*c+D*d;
                    if (m > F)
                        continue;
                    double density = m_salt / (double)m;
                    if (density > saturated)
                        continue;
                    // if (max_density < density) {
                    //     cout << FMT4(a,b,c,d) << endl;
                    //     cout << FMT2(m,m_salt) << endl;
                    //     cout << FMT2(max_density,density) << endl;
                    // }

                    if (chmax(max_density, density)) {
                        memo[0] = m;
                        memo[1] = m_salt;
                    }
                }
            }
        }
    }


    cout << memo[0] SP memo[1] << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <unordered_map>
//#include"testlib.h"
#define endl "\n"
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define RT(s) return cout<<s,0
#define sz(s)    (int)(s.size())
#define PI acos(-1)
#define EPS 1e-8
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
	//freopen("street.in", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
}
void fast() {
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
}
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}


int main() {
	file();
	fast();
	int a, b, c, k; cin >> a >> b >> c >> k;
	int ans = 0;
	int mn = min(k, a);
	ans += mn;
	k -= mn;
	mn = min(k, b);
	k -= mn;
	mn = min(k, c);
	ans += mn * -1;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
#include <string>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)
#pragma GCC optimize("unroll-loops")

#define DEBUG(x) cout << ">> " << #x << ": " << x << endl;
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;

int main() { _
  ll n; cin >> n;
  vector<ll> v(n);
  ll total = 0;
  for (ll i = 0; i < n; i++) {
    cin >> v[i];
  }
  for (ll i = 0; i < 64; i++) {
    ll oc=0, zc=0;
    for (ll j = 0; j < n; j++) {
      if (v[j]&1) oc++;
      else zc++;
      v[j] /= 2;
    }
    ll sum = ((oc*zc)%MOD) * ((ll(1)<<i)%MOD);
    total += sum%MOD;
    total %= MOD;
  }
  cout << total << endl;
  return 0;
}

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

UL N;
string S,T;
const ULL M = 1000000007;
ULL dp[26] = {};

int main(){
  cin >>N>>S>>T;
  dp[S[0]-'a']=1;
  for(UL i=1; i<N-1; i++){
    dp[S[i]-'a'] += dp[T[i]-'a'];
    dp[S[i]-'a'] %= M;
  }
  cout << dp[T[N-1]-'a'] << endl;
  return 0;
}


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

#define REP( i, n )     for( int (i) = 0; (i) < (n); (i)++ )
#define ALL( a )        (a).begin(), (a).end()

using namespace std;
using ll = long long;
using P = pair<int, int>;

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; }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

int main(){
    int N; cin >> N;
    vector<int> L( N );
    REP( i, N ) cin >> L[i];

    sort( ALL( L ) );

    ll ans = 0;
    REP( i, N  - 2 ){
        int a = L[i];
        for( int j = i + 1; j < N - 1; j++ ){
            int b = L[j];

            int maxc = a + b - 1;
            if( maxc < b ) continue;

            ans += upper_bound( ALL( L ), maxc ) - L.begin() - ( j + 1 );
        }
    }

    cout << ans << endl;

}


Measured memory_bytes: 256
t = list(input())
ans = 0
if t[0]=="?":
    t[0]="D"
    ans += 1

for i in range(1,len(t)):
    if (t[i]=="P"):
        pass
    elif (t[i]=="D"):
        ans += 1
        if (t[i-1]=="P"):
            ans += 1
    else:
        if (t[i-1]=="P"):
            ans += 2
            t[i]="D"
        else:
            ans+=1
            t[i]="D"
a = ""
for i in t:
    a += i
            
print(a)

Measured memory_bytes: 10924
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++)
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

LL n,ans=0;

bool check(LL x)
{
	LL n7=0,n5=0,n3=0;
	while(x>0)
	{
		if(x%10==7) n7++;
		if(x%10==5) n5++;
		if(x%10==3) n3++;
		x/=10;
	}
	return n7>0&&n5>0&&n3>0;
}

void dfs(LL x)
{
	if(x>n) return;
	//cout<<x<<' ';
	if(check(x)) ans++;
	dfs(x*10+7);
	dfs(x*10+5);
	dfs(x*10+3);
}

int main()
{
	cin>>n;
	dfs(0LL);
	cout<<ans<<endl;
	rt0;
}

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

using namespace std;

void solve()
{
	int N, K;
	while(cin >> N >> K)
	{
		if(!N && !K)
		{
			break;
		}
		vector<int> S(K);
		vector<vector<int> > B(N);
		for(int i = 0; i < N; ++i)
		{
			B[i].resize(K);
		}
		for(int i = 0; i < K; ++i)
		{
			cin >> S[i];
		}
		for(int i = 0; i < N; ++i)
		{
			for(int j = 0; j < K; ++j)
			{
				cin >> B[i][j];
			}
		}
		bool flag = true;
		for(int i = 0; i < K; ++i)
		{
			int sum = 0;
			for(int j = 0; j < N; ++j)
			{
				sum += B[j][i];
			}
			if(S[i] < sum)
			{
				flag = false;
				break;
			}
		}
		if(flag)
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No" << endl;
		}
	}
}

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

Measured memory_bytes: 0
#include <iostream>

using namespace std;

int main(){
    int a;
    int b;
    cin >> a >> b;
    if(a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0){
        cout << "Possible" << endl;
    }
    else{
        cout << "Impossible" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
#define chmax(x,y) x = max(x,y)

 
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int> > VVI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<bool> VB;
typedef vector<LL> VL;
typedef vector<vector<long long>> VVLL;
typedef vector<set<int>> VSI;
const int MOD = 1e9+7;
const int INF = 1e9;
const LL LINF = 1e18;
int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

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

int main() {
    int n;
    cin >> n;
    vector<LL> a(n);
    rep(i,n) cin >> a[i];
    LL t = 1000;
    LL k = 0;

    rep(i,n-1) {
        if(a[i+1] > a[i]) {
            k = t / a[i];
            t -= a[i] * k;
            t += a[i+1] * k;
        }
    }
    cout << t << endl;
}


Measured memory_bytes: 3624