akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll n,k;
    cin >> n >> k;
    vector<ll> a(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i);
    }
    sort(all(a));
    ll sup = 2e18;
    ll inf = -2e18;
    while(sup != inf){
        ll tmp;
        if(sup + inf < 0) tmp = (sup+inf-1)/2;
        else tmp = (sup+inf)/2;
        ll cnt = 0;
        for(i = 0;i < n;++i){
            if(a.at(i) < 0){
                ll ind = lower_bound(all(a), ((long double)tmp)/((long double)a.at(i))) - a.begin();
                cnt += n-ind;
            }else if(a.at(i) > 0){
                ll ind = upper_bound(all(a), ((long double)tmp)/((long double)a.at(i))) - a.begin();
                cnt += ind;
            }else if(tmp >= 0) cnt += n;
            if(a.at(i)*a.at(i) <= tmp) --cnt;
        }
        if(cnt/2 >= k) sup = tmp;
        else inf = tmp+1;
    }
    cout << sup << endl;
    return 0;
}

Measured memory_bytes: 1792
import java.util.*;
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int rslt[] = new int[n]; 
        for(int i=0;i<n;i++){
        	String A = sc.next();
			String B = sc.next();
			int[][] DP = new int[A.length() + 1][B.length() + 1];
			for(int j=0;j<A.length()+1;j++){//DP初期化
			    DP[j][0] = 0;
			}
	    	for(int j=0;j<B.length()+1;j++){
			    DP[0][j] = 0;
			}
			for(int j = 1; j <= A.length(); j++) {
				for(int k = 1; k <= B.length(); k++) {
					if(A.charAt(j - 1) == B.charAt(k - 1)) {
						DP[j][k] = DP[j - 1][k - 1] + 1;
					}else {
						DP[j][k] = Math.max(DP[j - 1][k], DP[j][k - 1]);
					}
				}
			}
			System.out.println(DP[A.length()][B.length()]);
        }
    }
}



Measured memory_bytes: 64400
use std::io;
use std::str;

const MOD: i32 = 1_000_000_007;

fn solve<R: io::BufRead, W: io::Write>(scan: &mut Scanner<R>, out: &mut W) {
    let n: usize = scan.token();
    let m: usize = scan.token();

    let mut grid = Vec::new();
    for _ in 0..n {
        let row: Vec<char> = scan.token::<String>().chars().collect();
        grid.push(row);
    }
    let mut dp = vec![vec![0; m]; n];

    let mut wall = false;
    for j in 0..m {
        if grid[0][j] == '#' {
            wall = true;
        }
        dp[0][j] = if wall { 0 } else { 1 };
    }
    wall = false;
    for i in 0..n {
        if grid[i][0] == '#' {
            wall = true;
        }
        dp[i][0] = if wall { 0 } else { 1 };
    }

    for i in 1..n {
        for j in 1..m {
            if grid[i][j] == '#' {
                dp[i][j] = 0;
            } else {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
            }
        }
    }
    let ans = dp[n - 1][m - 1];
    writeln!(out, "{}", ans).ok();
}

fn main() {
    let (stdin, stdout) = (io::stdin(), io::stdout());
    let mut scan = Scanner::new(stdin.lock());
    let mut out = io::BufWriter::new(stdout.lock());
    solve(&mut scan, &mut out);
}

pub struct Scanner<R> {
    reader: R,
    buffer: Vec<String>,
}

impl<R: io::BufRead> Scanner<R> {
    pub fn new(reader: R) -> Self {
        Self {
            reader,
            buffer: vec![],
        }
    }

    pub fn token<T: str::FromStr>(&mut self) -> T {
        loop {
            if let Some(token) = self.buffer.pop() {
                return token.parse().ok().expect("Failed parse");
            }
            let mut input = String::new();
            self.reader.read_line(&mut input).expect("Failed read");
            self.buffer = input.split_whitespace().rev().map(String::from).collect();
        }
    }

    pub fn tokens<T: str::FromStr>(&mut self) -> Vec<T> {
        assert!(self.buffer.is_empty());
        let mut input = String::new();
        self.reader.read_line(&mut input).expect("Failed read");
        input
            .split_whitespace()
            .map(|x| x.parse().ok().expect("Failed parse"))
            .collect()
    }
}


Measured memory_bytes: 9900
#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 <iterator>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
	int N;
	cin >> N;
	for (int i = 0; i <= (N / 4); i++) {
		for (int j = 0; j <= (N / 7); j++) {
			if (4 * i + 7 * j == N) {
				cout << "Yes";
				return 0;
			}
		}
	}
	cout << "No";
	return 0;
}

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

int main(){

  for(int n, p;cin >> n >> p, n|p;){
    int a[55] = {}, i = 0, v = p;
    while(a[i] != p){
      if(!v){ v = a[i], a[i] = 0; }
      else{ --v; ++a[i]; }
      i = ++i%n;
    }
    cout << i << endl;
  }

}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>

using namespace std;

int main(){
    int N,count=1;
    cin>>N;
    int A[N];
    for(int i=0;i<N;i++) cin>>A[i];
    int check=0;
    for(int i=0;i<N-1;i++){
        if(A[i]<A[i+1]){
            if(check==2){
                count++;
                check=0;
            }else check=1;
        }else if(A[i]>A[i+1]){
            if(check==1){
                count++;
                check=0;
            }else check=2;
        }
    }
    cout<<count;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
using ll = long long;
ll p = 1000000007ll;

ll n,k;
vector<ll> a;

bool reachable(ll fac)
{
  vector<ll> mo(a.begin(),a.end());
  for(ll&x:mo) x%=fac;
  sort(mo.begin(),mo.end());
  ll opt = p;
  REP(div,n+1) {
    ll suma = 0ll;
    ll sumb = 0ll;
    REP(i,div) {
      suma += mo[i];
    }
    FOR(i,div,n) {
      sumb += fac-mo[i];
    }
    opt = min(opt,max(suma,sumb));
  }
  if(opt<=k) return true;
  else return false;
}

int main(void)
{
  cin >> n >> k;
  a.resize(n);
  for(ll&x:a) cin >> x;
  ll sum = 0ll;
  for(ll x:a) sum+=x;
  vector<ll> factors;
  FOR(i,1,sum) {
    if(i*i>sum) break;
    if(sum%i == 0) {
      factors.push_back(i);
      factors.push_back(sum/i);
    }
  }
  ll answer = 1;

  for(ll fac:factors) {
    if(reachable(fac)) answer = max(answer, fac);
  }

  cout << answer << endl;

  return 0;
}


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

# define NMAX 1000000001

// void change(int b, int c, std::vector<int> &seq){
//     for(int i=0; i < b; i++){
//         if(seq.at(i) < c){
//             seq.at(i) = c;
//         }else{
//             return;
//         }
//     }
// }
//
// void map_change(){
//
// }

int main(){
    int N, M;
    cin >> N >> M;
    std::vector<int> seq(N);
    for(int i=0; i < N; i++){
        cin >> seq.at(i);
    }
    vector<std::vector<int> > ope(M, vector<int>(2));
    std::map<int, int> ope_map;
    // for(int i=0; i < M; i++){
    //     cin >> ope.at(i).at(0) >> ope.at(i).at(1);
    // }
    int a, b;
    for(int i=0; i < M; i++){
        cin >> a >> b;
        if(ope_map.count(b)){
            ope_map[b] += a;
        }else{
            ope_map[b] = a;
        }

    }
    sort(seq.begin(), seq.end());
    std::vector<int> ope_seq(N, 0);
    int pointer = 0;
    for (auto iter = ope_map.rbegin(); iter != ope_map.rend(); ++iter){
        // cout << iter->first << endl;
        int len = pointer + iter->second;
        for(int i=pointer; i < len; i++){
            ope_seq.at(i) = iter->first;
            // cout << iter->first << endl;
            pointer ++;
            if(pointer >= N){
                break;
            }
        }
        if(pointer >= N){
            break;
        }
    }
    sort(ope_seq.begin(), ope_seq.end());
    // for(int i=0; i < N; i++){
    //     cout << seq.at(i) << " ";
    // }
    // cout << endl;
    // for(int i=0; i < N; i++){
    //     cout << ope_seq.at(i) << " ";
    // }
    // cout << endl;
    std::vector<int>::iterator iter_ope = ope_seq.end() - 1;
    std::vector<int>::iterator iter_seq = seq.end() - 1;
    long sum = 0;
    for(int i=0; i < N; i++){
        if(*iter_ope > *iter_seq){
            sum += *iter_ope;
            iter_ope --;
        }else{
            sum += *iter_seq;
            iter_seq --;
        }
    }


    // for(int i=0; i < M; i++){
    //     change(ope.at(i).at(0), ope.at(i).at(1), seq);
    // }
    // long sum = accumulate(seq.begin(), seq.end(), 0);
    cout << sum << endl;
}


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

int main(){
int N, M=200; cin >> N; string S[N]; int d[N][N];
for(int i=0; i<N; i++){ cin >> S[i];
for(int j=0; j<N; j++){ if(i==j){d[i][j]=0;}else{d[i][j]=(S[i][j]=='1')?1:M;} }
}

for(int k=0; k<N; k++){ for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ 
  d[i][j]=min(d[i][j], d[i][k]+d[k][j]);
}}}
  
for(int k=0; k<N; k++){ for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ 
  if((d[i][j]+d[i][k]+d[k][j])%2){cout << -1 << "\n"; return 0;}
}}}
  
int ans=0;  
for(int i=0; i<N-1; i++){ for(int j=i+1; j<N; j++){ ans=max(ans, d[i][j]); }}
cout << ans+1 << "\n";
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9+100;
const ll MOD = 1e9+7;
const bool debug = 0;
//-----------------------------------------------//

int main() {
	int c[3][3];
	REP(i, 3) REP(j, 3) cin >> c[i][j];
	
	bool ans = true;
	FOR(j, 1, 3) {
		ans &= c[1][0] - c[0][0] == c[1][j] - c[0][j];
		ans &= c[2][0] - c[0][0] == c[2][j] - c[0][j];
	}
	FOR(i, 1, 3) {
		ans &= c[0][1] - c[0][0] == c[i][1] - c[i][0];
		ans &= c[0][2] - c[0][0] == c[i][2] - c[i][0];
	}
	
	puts(ans ? "Yes" : "No");
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool good[1000005];
int a[200005], rep[1000005];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	vector<int>v;
	memset(rep, 0, sizeof rep);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		rep[a[i]]++;
		v.push_back(a[i]);
	}
	sort(v.begin(), v.end());
	memset(good, 0, sizeof good);
	for(int i=0;i<n;i++){
		if(i>0) if(v[i]==v[i-1]) continue;
		for(int j=v[i]*2;j<=1000000;j+=v[i]){
			good[j]=true;
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(!good[a[i]] && rep[a[i]]==1){
			cnt++;
		}
	}
	cout<<cnt;
}


Measured memory_bytes: 9740
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.Closeable;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main implements Runnable {
    static ContestScanner in;
    static Writer out;
    public static void main(String[] args) {
        new Thread(null, new Main(), "", 16 * 1024 * 1024).start();
    }

    public void run() {
        Main main = new Main();
        try {
            in = new ContestScanner();
            out = new Writer();
            main.solve();
            out.close();
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    void solve() throws IOException {
        int n = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        System.out.println((n * a >= b) ? b : n * a);
    }
}


@SuppressWarnings("serial")
class MultiSet<T> extends HashMap<T, Integer>{
    @Override public Integer get(Object key){return containsKey(key)?super.get(key):0;}
    public void add(T key,int v){put(key,get(key)+v);}
    public void add(T key){put(key,get(key)+1);}
    public void sub(T key){final int v=get(key);if(v==1)remove(key);else put(key,v-1);}
    public MultiSet<T> merge(MultiSet<T> set)
    {MultiSet<T>s,l;if(this.size()<set.size()){s=this;l=set;}else{s=set;l=this;}
        for(Entry<T,Integer>e:s.entrySet())l.add(e.getKey(),e.getValue());return l;}
}

class Writer extends PrintWriter{
    public Writer(String filename)throws IOException
    {super(new BufferedWriter(new FileWriter(filename)));}
    public Writer()throws IOException{super(System.out);}
}
class ContestScanner implements Closeable{
    private BufferedReader in;private int c=-2;
    public ContestScanner()throws IOException
    {in=new BufferedReader(new InputStreamReader(System.in));}
    public ContestScanner(String filename)throws IOException
    {in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}
    public String nextToken()throws IOException {
        StringBuilder sb=new StringBuilder();
        while((c=in.read())!=-1&&Character.isWhitespace(c));
        while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public String readLine()throws IOException{
        StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();
        while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public long nextLong()throws IOException,NumberFormatException
    {return Long.parseLong(nextToken());}
    public int nextInt()throws NumberFormatException,IOException
    {return(int)nextLong();}
    public double nextDouble()throws NumberFormatException,IOException
    {return Double.parseDouble(nextToken());}
    public void close() throws IOException {in.close();}
}

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

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

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

int main() {
  int N, M, R;
  cin >> N >> M >> R;

  vector<int> r(R);
  rep(i, R) {
    cin >> r[i];
    r[i]--;
  }

  vector<vector<int>> d(N, vector<int>(N, INF));

  vector<int> A(M), B(M), C(M);
  rep(i, M) {
    cin >> A[i] >> B[i] >> C[i];
    A[i]--;
    B[i]--;
    d[A[i]][B[i]] = C[i];
    d[B[i]][A[i]] = C[i];
  }
  rep(i, N) {
    d[i][i] = 0;
  }

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

  int perm = 1;
  repp(i, 1, R) {
    perm *= i;
  }

  int ans = INF;
  for (int i = 0; i < perm; ++i) {
    int temp = 0;
    rep(j, R - 1) {
      temp += d[r[j]][r[j + 1]];
    }
    chmin(ans, temp);
    next_permutation(r.begin(), r.end());
  }

  cout << ans << endl;
}

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

int main(){
	int n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	int ans(0),rl(0),edge(0);
	rep(i,n-1){
		if(s[i] == s[i+1]){
			ans++;
		}else if(s[i] == 'R' && s[i+1] == 'L'){
			rl++;
		}
	}
	ans += 2 * min(rl,k);
	if(k-rl >= 1){
		ans = n-1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for(int i = 0; i < n; i++) {
        cin >> x[i];
        y[i] = x[i];
    }
    sort(y.begin(), y.end());
    int left = y[n/2 - 1];
    int right = y[n/2];
    int median = left + right;
    for (int i = 0; i < n; i++) {
        if (x[i] * 2 < median) {
            cout << right << endl;
        } else {
            cout << left << endl;
        }
    }
}


Measured memory_bytes: 3712
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
#define F first
#define S second
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> Pi;
int D,N;

int dijkstra(vector<vector<int> >& list,vector<vector<int> >& used)
{

  /*
  for(int i=0;i<D;i++)
    {
      cout << i+1 << " day" << endl;
      for(int j=0;j<list[i].size();j++)
	{
	  cout << list[i][j] << " ";
	}
      cout << endl;
    }
  */
  
  int mex = 0;
  queue<Pi> que;// Pi(P(value,day),pre_index)
  for(int i=0;i<list[0].size();i++)
    {
      que.push(Pi(P(0,1),i));
      used[0][i] = 0;
    }
  
  while(!que.empty())
    {
      Pi p = que.front(); que.pop();
      int total,day,pre_index;
      total = p.F.F, day = p.F.S, pre_index = p.S;

      if(day >= D)
	{
	  mex = max(mex,total);
	  continue;
	}

      for(int i=0;i<list[day].size();i++)
	{
	  int sum = total + abs(list[day-1][pre_index]-list[day][i]);
	  if(used[day][i] >= sum)
	    continue;

	  used[day][i] = sum;
	  que.push(Pi(P(sum,day+1),i));
	}

    }

  return mex;
}


int main()
{

  cin >> D >> N;
  vector<int> T;
  vector<vector<int> > list,used;
  list.resize(D),used.resize(D);


  for(int i=0;i<D;i++)
    {
      int in; cin >> in;
      T.push_back(in);
    }

  for(int j=0;j<N;j++)
    {
      int A,B,C;
      cin >> A >> B >> C;
      for(int k=0;k<D;k++)
	{
	  if(A <= T[k] && T[k] <= B)
	    {
	      list[k].push_back(C),used[k].push_back(-1);
	    }
	}
    }
  cout << dijkstra(list,used) << endl;


  return 0;
}

Measured memory_bytes: 10088
n,k=map(int,input().split())
l=[0]*(k+1)
for i in range(k):
    num=(k-i)
    if k//num==1:
        l[num]=1
    else:
        ret=pow(k//num,n,10**9+7)
        for j in range(2,k//num+1):
            ret-=l[num*j]
            ret%=(10**9+7)
        l[num]=(ret)%(10**9+7)
ans=0
for i in range(k+1):
    ans+=(l[i]*i)%(10**9+7)
print(ans%(10**9+7))

Measured memory_bytes: 74580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define INT(str) stoi((str), 0)
#define INTB(str) stoi((str), 0, 2) // 2進数の文字列を int に
//cout << fixed << setprecision(15);

int main() {
  int n, x, t;
  cin >> n >> x >> t;
  cout << t * (n / x + (n % x != 0)) << endl;
}


Measured memory_bytes: 3628
/* This Template is property of Pranav Khiste aka desmond_kaneki*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi(x,n) for(ll i=x;i<n;i++)
#define fj(x,n) for(ll j=x;j<n;j++)
#define vll vector<ll>
#define pb push_back
#define qll queue<ll>
#define mp make_pair
#define fst first
#define snd second
#define pll pair<ll,ll>
#define vpll vector<pll>
#define debug(x) cout<<#x<<' '<<x<<endl;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define mod 1000000007
#define SUP LLONG_MAX
#define INF LLONG_MIN
#define test() ll var;  cin>>var; while(var--)
#define fileio freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout);  // use cin cout only!!
main()
{
    fastio;
    ll x;
    cin>>x;
    ll ans;
    if(x>=400&&x<600)
        ans=8;
    else if(x<800)
        ans=7;
    else if(x<1000)
        ans=6;
    else if(x<1200)
        ans=5;
    else if(x<1400)
        ans=4;
    else if(x<1600)
        ans=3;
    else if(x<1800)
        ans=2;
    else
    {
        ans=1;
    }
    cout<<ans<<endl;
    
}


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

int main(){
  int k; cin >> k;
  int ans = 0;
  for(int i = 1; i <= k; i++){
    for(int j = 1; j <= k; j++){
      for(int n = 1; n <= k; n++){
        int cnt = __gcd(__gcd(n,j),i);
        ans += cnt;
      }
    }
  }
  cout << ans << endl;
}
        
        

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

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF * 300 * 300;
const int MOD = 1e9+9;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

LL my_pow(int x, int y){
	LL a=1;
	REP(i,y){
		a *= x;
		a %= MOD;
	}
	return a % MOD;
}
void Main()
{
	int n;
	cin >> n;
	string s,t;
	cin >> s >> t;

	REP(i,n){
		cout << s[i] << t[i];
	}
	cout << endl;

	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

Measured memory_bytes: 256
def solve(p, query):
    # the cost of group's all color change to i
    group_a = [0]*(color+1)
    group_b = [0]*(color+1)
    group_c = [0]*(color+1)

    for c_a, c_b, c_c in zip(mod_1, mod_2, mod_0):
        for i in range(1, color+1):
            group_a[i] += d[c_a][i]
            group_b[i] += d[c_b][i]
            group_c[i] += d[c_c][i]

    top_3_group_a = sorted(
        list(zip(list(range(color+1)), group_a[1:])), key=lambda x: x[1])[:3]
    top_3_group_b = sorted(
        list(zip(list(range(color+1)), group_b[1:])), key=lambda x: x[1])[:3]
    top_3_group_c = sorted(
        list(zip(list(range(color+1)), group_c[1:])), key=lambda x: x[1])[:3]
    ans = float('inf')
    for i in top_3_group_a:
        for j in top_3_group_b:
            if i[0] != j[0]:
                for k in top_3_group_c:
                    if i[0] != k[0] and j[0] != k[0]:
                        ans = min(ans, i[1]+j[1]+k[1])
    return ans


if __name__ == '__main__':
    n, color = map(int, input().split())
    c, d = [], []
    d.append([0]*(color+1))

    for _ in range(color):
        d.append([0]+list(map(int, input().split())))

    _c = []
    for _ in range(n):
        _c.append(list(map(int, input().split())))

    mod_1, mod_2, mod_0 = [], [], []

    for i in range(n):
        for j in range(n):
            if (i+j) % 3 == 1:
                mod_1.append(_c[i][j])
            elif (i+j) % 3 == 2:
                mod_2.append(_c[i][j])
            else:
                mod_0.append(_c[i][j])

    if n % 3 == 1:
        mod_1.append(0)
        mod_2.append(0)
    if n % 3 == 2:
        mod_0.append(0)
        mod_2.append(0)

    print(solve(c, d))


Measured memory_bytes: 7796
#include<iostream>
#include<iomanip>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
#include<memory>
using namespace std;
using ll=long long;

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

    vector<int> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    
    int lb = 0;
    int ub = 1e9+1;
    while(ub-lb>1){
        int mid = (lb+ub)/2;
        ll cnt = 0;
        for(int i=0;i<n;i++){
            // mid*p>=a[i]
            ll p = (a[i]+mid-1)/mid;
            cnt+=(p-1);
        }
        if(cnt>k) lb = mid;
        else ub = mid;
    }
    cout<<ub<<endl;
    

    
    
    
    
    return 0;
}


Measured memory_bytes: 4028
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

//                  876543210987654321
const long long MX=1000000000000000000ll;

int N;
long long K[64];

long long count(long long x,int id){
	long long a=1ll<<id;
	long long t=(x+1)/a;
//	printf("%lld %d %d\n",x,id,(t/2)*a);
	long long res=(t/2)*a;
	if(t%2==1){
		res+=(x+1)%a;
	}
	return res;
}

long long solve(long long W){
	//[A,A+W-1]
	//return A
	if(W==1){
		long long res=0;
		for(int i=N-1;i>=0;i--){
			if(K[i]==1) res+=(1ll<<i);
		}
		if(res>MX) return -1;
		return res;
	}
	long long A=-1;
	long long tmp=0;
	for(int i=N-1;i>=1;i--){
		if(K[i]==W){
			tmp+=(1ll<<i);
			continue;
		}else if(K[i]==0){
			continue;
		}
		tmp+=(1ll<<i);
		long long zeros=W-K[i];
		tmp-=zeros;
		A=tmp;
		break;
	}
//	if(dbg) printf("A=%lld\n",A);
	if(A==-1){
		A=tmp;
	}
	if(A==0) return -1;
	long long B=A+W-1;
	if(B>MX||A>MX) return -1;
	for(int i=0;i<N;i++){
		long long cur=count(B,i)-count(A-1,i);
		if(K[i]!=cur) return -1;
	}
	return A;
}

void solve(){
	if(N==64&&K[63]>0){
		printf("None\n");
		return;
	}
	if(N==1){
		printf("1 1\n");
		return;
	}
	long long A=-1,B=-1;
	for(long long W=K[0]*2-1;W<=K[0]*2+1;W++){
		long long cand=solve(W);
	//	printf("W=%lld->cand=%lld\n",W,cand);
		if(A!=-1&&cand!=-1){
			printf("Many\n");
			return;
		}
		if(A==-1&&cand!=-1){
			A=cand;
			B=cand+W-1;
		}
	}
	if(A==-1){
		printf("None\n");
		return;
	}
	printf("%lld %lld\n",A,B);
}

int main(){
	while(true){
		scanf("%d",&N);
		if(N==0) break;
		for(int i=0;i<N;i++) scanf("%lld",K+i);
		solve();
	}
	return 0;
}

Measured memory_bytes: 1040
object Main extends App {
  val n = io.StdIn.readInt()
  println(phi(n))

  def phi(n: Int): Int =
    if (isPrime(n)) n-1
    else {
      val pfs = primeFactors(n)
      val x = pfs.foldLeft(n.toDouble)((acc, e) => (acc*(e-1))/e)
      x.toInt
    }
  def primeFactors(n: Int): Seq[Int] = {
    if (n == 1) Seq()
    else if (isPrime(n)) Seq(n)
    else {
      var x = n
      val p = rho(n)
      if (isPrime(p)) {
        while(x % p == 0) x /= p
        p +: primeFactors(x)
      }
      else {
        val ps = primeFactors(p)
        ps foreach (p => while(x % p == 0) x /= p)
        ps ++ primeFactors(x)
      }
    }
  }
  def rho(n: Int): Int = {
    def f(x: Int, c: Int): Int = (x * x + c) % n
    def loop(x: Int, y: Int, d: Int, c: Int = 1): Int =
      if (d != 1) {
        if (d == n) loop(2,2,1,c+1)
        else d
      }
      else {
        val a = f(x, c)
        val b = f(f(y, c), c)
        loop(a, b, gcd(Math.abs(a-b), n), c)
      }
    if (n % 2 == 0) 2
    else loop(2,2,1)
  }
  def gcd(x: Int, y: Int): Int = {
    if (x < y) gcd(y, x)
    else {
      if (y > 0) {
        val r = x % y
        gcd(y, r)
      } else x
    }
  }
  def isPrime(n: Int): Boolean = Primes.miller_rabin_test(n)
  object Primes {
    private def mod_exp(x: BigInt, n: Int, m: Int): BigInt = {
      def loop(x: BigInt, n: Int, acc: BigInt): BigInt = {
        if (n == 0) acc
        else loop (
          (x * x) % m,
          n >> 1,
          if ((n & 1) == 1) (acc * x) % m else acc
        )
      }
      loop(x,n,1)
    }
    private def div_pow_2(d: Int, s: Int = 0): (Int, Int) ={
      if ((d % 2) != 0) (d,s)
      else div_pow_2(d/2, s+1)
    }

    private def miller_rabin(n: Int, a: Int): Boolean = {
      val (d,s): (Int, Int) = div_pow_2(n-1)
      val a_exp_d: BigInt = mod_exp(a,d,n)
      def double(x: BigInt): BigInt = mod_exp(x,2,n)
      def loop(e: BigInt, i: Int): Boolean = {
        if (i == 0) false
        else if (e == n-1) true
        else loop(double(e), i-1)
      }
      a_exp_d == 1 || loop(a_exp_d, s)
    }
    def miller_rabin_test(n: Int, k: Int = 20): Boolean = {
      def loop(i: Int): Boolean = {
        if (i == 0) true
        else {
          val a = scala.util.Random.nextInt(n-1)+1
          if (miller_rabin(n,a)) loop(i-1)
          else false
        }
      }
      if (n < 2) false
      else loop(k)
    }
  }
}

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

// region template
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll gcd(ll a, ll b) { return __gcd(a, b); }

ll euclid(ll a, ll b, ll &x, ll &y) {
    if (b) { ll d = euclid(b, a % b, y, x);
        return y -= a/b * x, d; }
    return x = 1, y = 0, a;
}

typedef unsigned long long ull;
typedef long double ld;
ull mod_mul(ull a, ull b, ull M) {
    ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
    return ret + M * (ret < 0) - M * (ret >= (ll)M);
}
ull mod_pow(ull b, ull e, ull mod) {
    ull ans = 1;
    for (; e; b = mod_mul(b, b, mod), e /= 2)
        if (e & 1) ans = mod_mul(ans, b, mod);
    return ans;
}

const ll mod = 1000000007;
struct Mod {
    ll x;
    Mod(ll xx) : x(xx) {}
    Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
    Mod operator-(Mod b) { return Mod((x - b.x) % mod); }
    Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
    Mod operator/(Mod b) { return *this * invert(b); }
    Mod invert(Mod a) {
        ll x, y, g = euclid(a.x, mod, x, y);
        assert(g == 1); return Mod((x + mod) % mod);
    }
    Mod operator^(ll e) {
        if (!e) return Mod(1);
        Mod r = *this ^ (e / 2); r = r * r;
        return e & 1 ? *this * r : r;
    }
};
// endregion

int main() {
    cin.sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit);

    string s; cin >> s;
    cout << count(all(s), '1') << endl;
}

Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
a = inpl()
res = INF
for i in range(n-k+1):
    if a[i]*a[i+k-1] >= 0:
        res = min(res, max(abs(a[i]), abs(a[i+k-1])))
    else:
        c = min(abs(a[i]), abs(a[i+k-1]))
        d = max(abs(a[i]), abs(a[i+k-1]))
        res = min(res, c*2+d)
print(res)

Measured memory_bytes: 16268
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    private const long INFINITY = 9223372036854775807;
    public static void Main()
    {
        int H = NextInt();
        int W = NextInt();
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                string s = NextString();
                if (s == "snuke") { Console.WriteLine((char)(j + 65) + "" + (i + 1)); }
            }
        }
    }
}

public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 11220
#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>
#include <unordered_map>

using namespace std;
int N, K;
int x, y;
char c;
int sum[2001][2001];
int max(int a, int b,int c) {
  return max(max(a, b), c);
}

int main() {
  cin >> N >> K;
  for (int i=0; i<N; i++) {
    cin >> x >> y >> c;
    if (c == 'W') {
      x += K;
    }
    x = x%(2*K);
    y = y%(2*K);
    sum[x+1][y+1]++;
  }

  for (int i=0; i<2*K+1; i++) {
    for (int j=1; j<2*K+1; j++) {
      sum[i][j] += sum[i][j-1];
    }
  }
  for (int j=0; j<2*K+1; j++) {
    for (int i=1; i<2*K+1; i++) {
      sum[i][j] += sum[i-1][j];
    }
  }

  int ans = 0;
  for (int i=0; i<=K; i++) {
    for (int j=0; j<=K; j++) {
      int a = sum[i][j];
      int b = sum[i+K][j+K] - sum[i][j+K] - sum[i+K][j] + sum[i][j];
      int c = sum[2*K][2*K] - sum[2*K][j+K] - sum[i+K][2*K] + sum[i+K][j+K];
      int d = sum[2*K][j] - sum[i+K][j];
      int e = sum[i][2*K] - sum[i][j+K];
      ans = max(ans, a+b+c+d+e, N-(a+b+c+d+e));
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 15872
#include<cstdio>
#include<vector>
#include<functional>
#include<algorithm>

using namespace std;

int N,A,B,C;
vector<int> d;

int main()
{
  scanf("%d%d%d%d",&N,&A,&B,&C);

  for (int i = 0; i < N; i++) {
    int t;
    scanf("%d",&t);
    d.push_back(t);
  }

  sort(d.begin(), d.end(), greater<int>());

  int x = 0, y = 0;
  double z = 0;

  x = C;
  y = A;
  z = x / (double)y;

  for (vector<int>::iterator it = d.begin(); it != d.end(); it++) {
    x += *it;
    y += B;
    if (z > x / (double)y) break;
    z = x / (double)y;
  }

  printf("%d\n", (int)z);
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());

using ll = long long;
using ld = long double;
using P = pair<int, int>;

ll mod = 1e9 + 7;

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

  ll n, m;
  cin >> n >> m;
  ll a, b;
  vector<P> e(m);
  REP(i, m){
    cin >> a >> b;
    a--;
    b--;
    e[i] = P(b, a);
  }
  sort(e.begin(), e.end());
  ll ans = 0, cut = -1;
  REP(i, m){
    a = e[i].second, b = e[i].first;
    if(a <= cut && cut < b) continue;
    cut = b - 1;
    ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
import math

X = int(input())

def prime(x):
    if x >=3:
        if x % 2 == 0:
            return False
        else:    
            T = True
            i = 2
            while (T == True)&(1 < i <= math.ceil(math.sqrt(x))):
                if x % i == 0:
                    T = False
                i +=1
            return T
    else:
        return True

if X == 2:
    print(2)
elif X % 2 == 0:
    T = X + 1
    while (prime(T) == False):
        T +=2
    print(T)
else:
    T = X
    while (prime(T) == False):
        T +=2
    print(T)

Measured memory_bytes: 3064
from collections import defaultdict
from bisect import *

def into_dict(dics,x,y,u):
  x,y = int(x),int(y)
  insort(dics[u+'_x'][x],y)
  insort(dics[u+'_y'][y],x)
  insort(dics[u+'_xpy'][x+y],x)
  insort(dics[u+'_ymx'][y-x],x)
  return dics

def para(dics,dic1,dic2):
  ans = float('inf')
  for k,v in dics[dic1].items():
    for zahyou in v[1:-1]:
      ind = bisect_right(dics[dic2][k],zahyou)
      dis = zahyou-dics[dic2][k][ind-1]
      ans = min(ans,dis)
  return ans

def solve():
  ans = []
  N = int(input())
  dics = defaultdict(lambda: defaultdict(lambda: [-float('inf'),float('inf')]))
  for i in range(N):
    dics = into_dict(dics,*input().split())
  lis1 = [['L_y','R_y'],['D_x','U_x']]
  lis2 = [['L_ymx','U_ymx'],['U_xpy','R_xpy'],['L_xpy','D_xpy'],['D_ymx','R_ymx']]
  for arg in lis1:
    ans.append(para(dics,*arg)*5)
  for arg in lis2:
    ans.append(para(dics,*arg)*10)
  ans = min(ans)
  return ans if ans<float('inf') else 'SAFE'
print(solve())

Measured memory_bytes: 253280
import copy
N, M = map(int, input().split())

pairs = []
for _ in range(M):
    a, b = map(int, input().split())
    pairs.append([a, b])

Nodes = [{} for i in range(N)]
for pair in pairs:
    a, b = pair
    a -= 1
    b -= 1
    Nodes[a][b] = 1
    Nodes[b][a] = 1


def dfs(i):
    isFound[i] = True
    for neighbor in tmp_Nodes[i]:
        if isFound[neighbor] == False:
            dfs(neighbor)


count = 0
for skip in range(M):
    tmp_Nodes = copy.deepcopy(Nodes)
    a, b = pairs[skip]
    a -= 1
    b -= 1
    tmp_Nodes[a].pop(b)
    tmp_Nodes[b].pop(a)

    isFound = [False for _ in range(N)]
    dfs(0)
    #print(isFound)
    for v in isFound:
        if v == False:
            count += 1
            break

print(count)


Measured memory_bytes: 3572
'import sys'
d=[[[0 for i in range(10)]for j in range(3)]for k in range(4)]
n=int(input())
for i in range(n):
    b,f,r,v=[int(j) for j in input().split()]
    d[b-1][f-1][r-1]+=v
for i, b in enumerate(d):
    for f in b:
        for r in f:
            print(" {}".format(r),end="")
        print()
    if i< 3:
        print("#"*20)


Measured memory_bytes: 5624
count = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]
N = int(input())
for i in range(N):
    b,f,r,v = map(int,input().split())
    count[b-1][f-1][r-1] += v
for i in range(4):
    for j in range(3):
        for k in range(10):
            print(f" {count[i][j][k]}",end = "")
        print()
    if i != 3:
        print("####################")


Measured memory_bytes: 5636
/*https://atcoder.jp/contests/abc156/tasks/abc156_c*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
// #ifndef ONLINE_JUDGE
// 	// for getting input from input.txt
// 	freopen("input.txt", "r", stdin);
// 	// for writing output to output.txt
// 	freopen("output.txt", "w", stdout);
// #endif
	int n, a[100];
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	int sum = 0, min_sum = 1e9, mina = a[0], max = a[n - 1];
	// cout << min << max << endl;
	for (int i = mina; i <= max; i++)
	{
		sum = 0;
		for (int j = 0; j < n; j++)
			sum += (a[j] - i) * (a[j] - i);
		min_sum = min(min_sum, sum);
	}
	cout << min_sum << endl;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,v) for (int i = 0; i < v.size(); i++)
#define RREPALL(i,v) for (int i = v.size()-1; i >= 0; i--)
#define SORT(v) sort(v.begin(), v.end())
#define MIN_ELEMENT(v) min_element(v.begin(), v.end())
#define MAX_ELEMENT(v) max_element(v.begin(), v.end())
#define COUNT(v,n) count(v.begin(), v.end(), n);
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

void AC(bool flag) {cout<<(flag ? "AC" : "WA")<<endl;}

int main()
{
    string s;
    cin>>s;
    bool flag = true;

    int cnum = 0;
    if (s[0] != 'A') {
        flag = false;
    } else {
        FOR(i,1,s.size()) {
            if (s[i] == 'C') {
                if (2 <= i && i <= s.size() - 2) {
                    cnum++;
                } else {
                    flag = false;
                    break;
                }
            } else if ('a' <= s[i] && s[i] <= 'z') {
                continue;
            } else {
                flag = false;
                break;
            }
        }
    }
    AC(flag && cnum == 1);

    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int h,n;
    cin >> h >> n;
    int a[n],b[n];
    for(int i = 0;i < n;i++)
    {
        cin >> a[i] >> b[i];
    }
    vector<vector<long long int> > dp(n + 1,vector<long long>(h + 1,INT_MAX));
    dp[0][0] = 0;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j <= h;j++)
        {
            dp[i + 1][j] = min(dp[i + 1][j],dp[i][j]);
            dp[i + 1][min(j + a[i],h)] = min(dp[i + 1][min(j + a[i],h)],dp[i + 1][j] + b[i]);
        }
    }
    cout << dp[n][h] << "\n";

    return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  
using vvll = vector< vector<ll> >;
using vll = vector<ll> ;
using pll = pair<ll, ll> ;

#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define I insert
#define ar array
#define endl '\n'
#define all(x) x.begin(), x.end()
#define sz(x) ((long long)x.size())

template<typename T> void umin(T& a,T b){a = min(a,b);}
template<typename T> void umax(T& a,T b){a = max(a,b);}

const ll maxs = 1e6+5;
const ll lmaxs = 20;
ll mod = 1e9+7;
ll oo = 1e15;


ll fast(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        y >>= 1;
    }
    return res;
}

void pre(){

    

}

void solve(){    

    int n;
    cin >> n;
    ll ans = (fast(10,n) - 2*fast(9,n) + fast(8,n))%mod;
    ans += mod;
    ans %= mod;
    cout << ans;    

}


int32_t main(){
    #ifndef ONLINE_JUDGE
    freopen("input00.txt","r",stdin);
    #endif
    IOS;
    pre();
    ll T = 1;
    //cin >> T;
    while(T--){
        solve();   
    }
    return 0;
}

Measured memory_bytes: 3644
// HEADERS //
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <stack>
#include <unordered_map>
#include <bitset>
 
// MISCELLANEOUS //
#define fast_IO() ios_base::sync_with_stdio(false),cin.tie(NULL)
#define gcd __gcd
#define cnt_1 __buitlin_popcount
#define ll long long
#define endl "\n"
#define scn_I(x) scanf("%d",&x)
#define scn_L(x) scanf("%lld",&x) 
#define test(t) cin>>t; while(t--)
#define mem(v,x) memset(v,x,sizeof(v))
 
// LOOPS //
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define irep(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define srep(i,v) for(decltype(v.begin())i=v.begin();i!=v.end();i++)
 
// CONTAINERS //
// #define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ii pair<int,int>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define msi map<string,int>
#define mll map<ll,ll>
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(v) (v).begin(),(v).end()
#define present(v,x) (v).find(x)!=(v).end()
 
// DEBUGGING //
#define dbg() printf("\n**DEBUG**\n") 
#define chk(a) cerr<<endl<<#a<<":"<<a<<endl
#define chk2(a,b) cerr<<endl<<#a<<":"<<a<<"\t"<<#b<<":"<<b<<endl
 
// CONSTANTS //
#define PI acos(-1)
#define M 1000000007
#define N 100005
 
// MAIN //
// using namespace __gnu_pbds; 
using namespace std;
int main()
{
  fast_IO();
  int n,k; cin>>n>>k; vi v(n);
  rep(i,0,n) cin>>v[i];
  ll dp[n]; mem(dp,0);
  rep(i,1,n) dp[i]=abs(v[i]-v[i-1]);
  rep(i,2,n)
  {
    dp[i]=abs(v[i]-v[i-1])+dp[i-1];
    for(int j=2;j<=k && j<=i;++j) dp[i]=min(dp[i],abs(v[i]-v[i-j])+dp[i-j]);
  }
  cout<<dp[n-1];
}

Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
    int a;
    string s;

    cin >> a >> s;
    
    if (a >= 3200)
    {
        cout << s << endl;
    }
    else
    {
        cout << "red" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 888
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N;
cin>>N;
vector<int> A(N);
for(int i=0;i<N;i++) cin>>A[i];
vector<int> rev(N);
for(int i=0;i<N;i++) rev[A[i]-1]=i+1;
for(int i=0;i<N;i++) cout<<rev[i]<<endl;
return 0;
}

Measured memory_bytes: 1664
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

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

	int n;
	cin >> n;

	vector<int> w(n);
	for (int i = 0; i < n; i++)
	{
		cin >> w.at(i);
	}

	ll res = inf;
	ll s0 = 0;
	for (int i = 0; i < n; i++)
	{
		s0 += w.at(i);
		ll s1 = 0;
		for (int j = i + 1; j < n; j++)
		{
			s1 += w.at(j);
		}
		res = min(res, abs(s0 - s1));
	}

	cout << res << endl;
}

Measured memory_bytes: 256
n = int(raw_input())
 
info = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]
 
for i in range(n):
    b, f, r, v = map(int, raw_input().split())
    b, f, r = b-1, f-1, r-1
    info[b][f][r] += v
 
sharp = False
for i in info:
    if sharp:
        print "#" * 20
    for j in i:
        print " "+" ".join(map(str, j))
    sharp = True

Measured memory_bytes: 6480
#ifdef MY_LOCAL
#define MY_NAMESPACE(ns) namespace ns {
#define MY_NAMESPACE_    }
#define MY_DEBUG(s)      s
#else
#define MY_NAMESPACE(ns) 
#define MY_NAMESPACE_    
#define MY_DEBUG(s)      
#endif

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

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

#define EPS (1e-7)
#define IINF ((int)1e9)


MY_NAMESPACE(testbed)
int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	ll res = 1;  // for k=1
	for (int k = 2; k <= n; k++)
	{
		res += 2 * (ll)k;  // for two divisors of 1 and k
	}
	for (int k = 2; k * 2 <= n; k++)
	{
		for (int j = k * 2; j <= n; j += k)
		{
			res += j;  // for the divisors other than 1 and k
		}
	}
	cout << res << "\n";
	return 0;
}
MY_NAMESPACE_

Measured memory_bytes: 3616
import java.util.Scanner;

class Main{
    final static int LEN = 105;
    public static void main(String args[]){
	Integer[][] graph = new Integer[LEN][LEN];
	int[] minCost = new int[LEN];
	int count=0;
	int v;
	Boolean[] used = new Boolean[LEN];

	Scanner in = new Scanner(System.in);

	//read
	int n = in.nextInt();
	for(int i=0; i<n; i++){
	    for(int j=0; j<n; j++){
		int k = in.nextInt();
		graph[i][j]=(k==-1? Integer.MAX_VALUE : k);
	    }
	}

	//make prim
	for(int i=0; i<n; i++){
	    minCost[i]=Integer.MAX_VALUE;
	    used[i]=false;
	}

	minCost[0]=0;

	while(true){
	    v = -1;
	    for(int i=0; i<n; i++){
		if(!used[i] && (v==-1 || minCost[i] < minCost[v]))v=i;
	    }

	    if(v==-1)break;
	    used[v]=true;
	    count+=minCost[v];

	    for(int i=0; i<n; i++){
		minCost[i]=Math.min(minCost[i], graph[v][i]);
	    }
	}

	//print
	System.out.println(count);
    }
}

Measured memory_bytes: 13000
K,T = map(int, input().split())

A = list(map(lambda x: -int(x), input().split()))

import heapq as hq

hq.heapify(A)

a = hq.heappop(A)

while A:
  if a == -1:
    a = hq.heappop(A)
  else:
    a = hq.heapreplace(A,a+1)

print(-a-1)

Measured memory_bytes: 3188