akhauriyash/Code-Regression huggingface dataset:
let input = readLine()!.split(separator: " ").map { Int($0)! }
let H = input[0]
let W = input[1]
let K = input[2]

enum Square: Character {
    case white = "."
    case black = "#"
}

var c = [[Square]]()
let numberOfRowCombinations = 1 << H
let numberOfColumnCombinations = 1 << W
var dp = Array(repeating: Array(repeating: Optional<Int>.none, count: numberOfColumnCombinations), count: numberOfRowCombinations)
dp[0][0] = 0

for _ in stride(from: 0, to: H, by: 1) {
    let row = Array(readLine()!).map { Square(rawValue: $0)! }
    c.append(row)
    dp[0][0]! += row.filter { $0 == .black }.count
}

for i in stride(from: 0, to: H, by: 1) {
    for state in stride(from: 0, to: numberOfRowCombinations, by: 1) {
        guard state & (1 << i) == 0,
            let value = dp[state][0] else { continue }
        let nextState = state | (1 << i)
        dp[nextState][0] = value - c[i].filter { $0 == .black }.count
    }
}

for j in stride(from: 0, to: W, by: 1) {
    for rowState in stride(from: 0, to: numberOfRowCombinations, by: 1) {
        for columnState in stride(from: 0, to: numberOfColumnCombinations, by: 1) {
            guard columnState & (1 << j) == 0,
                let value = dp[rowState][columnState] else { continue }
            let nextColumnState = columnState | (1 << j)
            var numberOfBlackSquares = 0
            for i in stride(from: 0, to: H, by: 1) {
                if rowState & (1 << i) == 0, c[i][j] == .black {
                    numberOfBlackSquares += 1
                }
            }
            dp[rowState][nextColumnState] = value - numberOfBlackSquares
        }
    }
}

let result = dp.reduce(0) { sum, row in
    sum + row.filter { $0 == K }.count
}
print(result)


Measured memory_bytes: 8332
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<bitset>

using namespace std;
typedef long long ll;
#define i_7 1000000007
#define i_5 1000000005
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=1000000000000;/*10^12*/
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}

/////////////////////////////////////////////////////

int main(){
    int n;cin>>n;
    int a[n],b[n],c[n];
    rep(i,0,n-1)cin>>a[i];
    rep(i,0,n-1)cin>>b[i];
    rep(i,0,n-1)cin>>c[i];
    sort(a,a+n);sort(b,b+n);sort(c,c+n);
    ll ans=0;
    rep(i,0,n-1){
        ans+=(c+n-upper_bound(c,c+n,b[i]))*(lower_bound(a,a+n,b[i])-a);
    }
    cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 1408
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner src = new Scanner(System.in);

		//配列array
		ArrayList<Integer> array = new ArrayList<Integer>();

		int n  = src.nextInt();

		//nに入力された数だけ繰り返し、配列に要素を代入
		for(int i=0; i<n; i++) {
			array.add(src.nextInt());
		}

		int q = src.nextInt();

		for(int i=0; i<q; i++) {

			int b = src.nextInt();
			int e = src.nextInt();
			int k = src.nextInt();

			int count = 0;
			
			for(int j = b; j < e; j++)
				if(array.get(j).equals(k))
					count++;
			System.out.println(count);
		}
	}
}


Measured memory_bytes: 43844
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

// 入次数と出次数がともに1である ⇒ 辺の向きが揃ったループ（v1 -> v2 -> ... -> vn -> v1）
// ⇒ ある点を出発して戻って来られるかを調べる
//
// ループを構成する経路が複数あれば、より短い方が条件を満たす（(v1 -> v2 -> v3, v1 -> v3)の場合、条件に合わない(v1,v2,v3)を採用しない）
// ⇒最短経路のループを探せば良い
int main() {
  int N;  // 頂点の数
  int M;  // 辺の数
  std::cin >> N >> M;

  // 頂点の親子関係のマップを作る
  std::unordered_map<int, std::vector<int>> children_map;  // 親頂点から子供を探すためのマップ
  for (int i = 0; i < M; ++i) {
    int A, B;  // AからBへの辺
    std::cin >> A >> B;
    children_map[A].push_back(B);
  }

  // 最短のループを探す
  std::vector<bool> visited(N + 1);  // 訪問を記録するフラグ列
  std::vector<int> path;             // 現在たどっている頂点の経路
  std::vector<int> shortest_path;    // 見つけたループの最短経路
  path.reserve(N + 1);
  shortest_path.reserve(N + 1);
  bool quit = false;  // 処理を終了するためのフラグ
  for (int start = 1; start <= N; ++start) {
    // 初期化
    std::fill(visited.begin(), visited.end(), false);
    path.clear();
    visited[start] = true;
    path.push_back(start);

    while (true) {
      // まだ訪問していない子頂点に訪問する
      bool all_visited = true;  // すべての子頂点が訪問済みだったか
      for (const auto& child : children_map[path.back()]) {
        if (child == start) {
          // 始点に戻ってこられる最短経路を記録する
          if (shortest_path.empty() || path.size() < shortest_path.size()) {
            shortest_path = path;

            // これ以上ない最短経路が見つかれば、そこで終了する
            if (shortest_path.size() == 2) {
              quit = true;
              break;
            }
          }
        } else if (!visited[child]) {
          // 未訪問の子頂点があれば、その先も訪問する
          path.push_back(child);
          visited[child] = true;
          all_visited = false;
          break;
        }
      }

      // これ以上ない最短経路が見つかれば、そこで終了する
      if (quit) break;

      // すべての子頂点が訪問済みとなれば、1つ前の頂点に戻る
      if (all_visited) {
        path.pop_back();

        // すべての頂点を確認し終えたら調査を終了する
        if (path.empty()) break;
      }
    }

    // これ以上ない最短経路が見つかれば、そこで終了する
    if (quit) break;
  }

  // 結果発表
  if (shortest_path.empty()) {
    // ループが見つからなかった場合
    std::cout << "-1";
  } else {
    // ループを見つけた場合
    std::cout << shortest_path.size() << '\n';
    for (const auto& v : shortest_path) {
      std::cout << v << '\n';
    }
  }

  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;

int main(){
    ll n,i,j,k;
    cin >> n;
    ll a[n + 1];
    for(i = 0; i < n;i++)
        cin >> a[i];
    ll dp[n][n], cost[n][n];
    for(i = 0; i < n;i++){
        for(j = 0; j < n;j++){
            dp[i][j] = 1e13;
            cost[i][j] = 1e13;
        }
        dp[i][i] = a[i];
        cost[i][i] = 0;
    }
    
    for(i = 2; i <= n;i++){
        for(j = 0; j <= n - i;j++){
            for(k = 1; k < i;k++){
                dp[j][j + i - 1] = min(dp[j][j + k - 1] + dp[j + k][j + i - 1], dp[j][j + i - 1]);
                cost[j][j + i - 1] = min(cost[j][j + k - 1] + cost[j + k][j + i - 1], cost[j][j + i - 1]);
            }
            cost[j][j + i - 1] += dp[j][j + i - 1];
        }
    }
    cout << cost[0][n - 1] << endl;
    return 0;
}

Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a,b,sum;
	cin>>a>>b;
	sum=b-a+1;
	if(a<b)
	{
		if(a>0&&b>0)
		{
			cout<<"Positive"<<endl;
		}
		else
		{
			if(a<=0&&b>0)
			{
				cout<<"Zero"<<endl;
			}
			else
			{
				if(a<0&&b<=0)
				{
					if(b==0)
					{
						cout<<"Zero"<<endl;
					}
					else
					{
						if(sum%2==0)
						{
							cout<<"Positive"<<endl;
						}
						else
						{
							cout<<"Negative"<<endl;
						}
					}
				}
			}
		}
	}
	else
	{
		return 0;
	}
	return 0;	
}

Measured memory_bytes: 256
class Transformation(object):

    def __init__(self, text):
        self.text = text

    def print(self, a, b):
        print(self.text[a:b+1])

    def reverse(self, a, b):
        target = self.text[a:b+1]
        target = target[::-1]
        self.text = self.text[:a] + target + self.text[b+1:]

    def replace(self, a, b, p):
        self.text = self.text[:a] + p + self.text[b+1:]


text = input()
t = Transformation(text)
q = int(input())
for i in range(q):
    commands = input().split()
    command = commands[0]
    a = int(commands[1])
    b = int(commands[2])
    if command == "print":
        t.print(a, b)
    elif command == "reverse":
        t.reverse(a, b)
    elif command == "replace":
        p = commands[3]
        t.replace(a, b, p)



Measured memory_bytes: 5624
// inputに入力データ全体が入る
function Main(input) {
  var a,p;
  a = Number(input.split('\n')[0].split(' ')[0]);
  p = Number(input.split('\n')[0].split(' ')[1]);
  console.log(Math.floor((a * 3 + p) / 2));
  
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 11468
N = int(input())
l = list(map(int, input().split()))
c = 0
for j in range(0,N-2):
    if l[j]<l[j+1]<l[j+2] or l[j+2]<l[j+1]<l[j] or (l[j]==l[j+2] and l[j]<l[j+1]) or (l[j]==l[j+2] and l[j]<l[j+1]) or (l[j]==l[j+1] and l[j+2]<l[j+1]) or (l[j+1]==l[j+2] and l[j]<l[j+1]):
        c+=1
print(c)


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		if(n > 88 || n % 10 == 9){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 22740
//https://blog.csdn.net/hesorchen
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 0x3f3f3f3f
#define MAX 100010
#define mod 1000000007
#define PI 3.1415925
int p[MAX];
int main()
{
    int n, k;
    cin >> n >> k;
    n--;
    k--;
    string a;
    cin >> a;
    int ans = n / k;
    if (n % k != 0)
        ans++;
    cout << ans << 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++)
using ll = long long;
int n[2], a, b, c, unzip[2][3005], *e[2], m[2], dp[3005][3005], dx[] = {1,-1,0,0}, dy[] = {0, 0,1,-1};
ll ans;
bool out[2][3005][3005], used[3005][3005];
tuple<int,int,int> forb[2][1005];
map<int, int> zip[2];
stack<pair<int,int>> st;
int main(){
	scanf("%d%d", n, n+1);
	e[0] = unzip[0]+1; e[1] = unzip[1]+1;
	rep(t,2) rep(i,n[t]){
		scanf("%d%d%d", &a, &b, &c);
		forb[t][i] = {a, (t?b:c), (t?c:b)};
		*e[0]++ = a;
		*e[t]++ = b;
		*e[1]++ = c;
	}
	rep(t,2){
		sort(unzip[t],e[t]);
		e[t] = unique(unzip[t], e[t]);
		m[t] = e[t] - unzip[t];
		if(unzip[t][m[t]-1] == 0) return 0 * puts("INF");
		rep(i,m[t]) zip[t][unzip[t][i]] = i;
	}
	rep(t,2) rep(i,n[t]){
		auto [a, b, c] = forb[t][i];
		a = zip[0][a]; b = zip[1][b]; c = zip[t][c];
		if(t) for(; b < c; b++) out[!t][a][b] = true;
		else for(; a < c; a++) out[!t][a][b] = true;
	}
	st.emplace(zip[0][0],zip[1][0]); used[zip[0][0]][zip[1][0]] = true;
	while(!st.empty()){
		auto [x, y] = st.top(); st.pop();
		ans += (ll)(unzip[0][x+1] - unzip[0][x]) * (unzip[1][y+1] - unzip[1][y]);
		rep(t,4){
			int nx = x + dx[t], ny = y + dy[t];
			if(t%2 == 0 && out[t/2][nx][ny]) continue;
			if(t%2 == 1 && out[t/2][x][y]) continue;
			if(used[nx][ny]) continue;
			if(nx < 0 || m[0] <= nx || ny < 0 || m[1] <= ny) return 0 * puts("INF");
			used[nx][ny] = true;
			st.emplace(nx,ny);
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 57800
#include<iostream>
#include<algorithm>
using namespace std;
int t[3],x,y;
int a=0,b=0,c=0;
int main(){
  while(1){
    cin>>t[0]>>t[1]>>t[2];
    sort(t,t+3);
    x=t[0]*t[0]+t[1]*t[1];
    y=t[2]*t[2];
    if(t[0]+t[1]<=t[2]){
      break;
    }else if(x==y){
      a++;
    }else if(x>y){
      b++;
    }else if(x<y){
      c++;
    }
  }
  cout<<a+b+c<<' '<<a<<' '<<b<<' '<<c<<endl;
  return 0;
}

Measured memory_bytes: 1176
n = int(input())

def prime_factorize(n):
    fac = []
    if n < 2: return fac
    while n%2 == 0:
        n //= 2
        fac.append(2)
    for i in range(3,int(n**0.5)+1,2):
        while n%i == 0:
            n //= i
            fac.append(i)
    if n != 1: fac.append(n)
    return fac

print("{}: {}".format(n," ".join(map(str,prime_factorize(n)))))


Measured memory_bytes: 5640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <climits>
#include <map>
#include <set>
const int mod = 1e9 + 7;
const int inf = 1 << 20;
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
using namespace std;


int main()
{
    string s;
    cin >> s;
    if(s == "SUN") cout << 7;
    if(s == "MON") cout << 6;
    if(s == "TUE") cout << 5;
    if(s == "WED") cout << 4;
    if(s == "THU") cout << 3;
    if(s == "FRI") cout << 2;
    if(s == "SAT") cout << 1;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstring>
#include <cstdio>
#include<cmath>

typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;

int main ()
{
    int n,i,j,sum=0;
    cin>>n;
    int arr[n];
    for (i=0;i<n;i++)
    {
        cin>>arr[i];
    }

    for(i=0;i<n-1;i++)
    {
        for (j=i+1;j<n;j++)
        {
            sum+=(arr[i]*arr[j]);
        }
    }
    cout<<sum<<endl;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(int (i) = (int)(a); (i) < (int)(n); ++(i))
#define FORe(i, a, n) for(int (i) = (int)(a); (i) <= (int)(n); ++(i))
#define rFOR(i, a, n) for(int (i) = (int)(n)-1; (i) >= (int)(a); --(i))
#define rFORe(i, a, n) for(int (i) = (int)(n); (i) >= (int)(a); --(i))
#define REP(i, n) FOR((i), 0, (n))
#define REPe(i, n) FORe((i), 1, (n))
#define REPo(i, n) FORe((i), 0, (n))
#define rREP(i, n) rFOR((i), 0, (n))
#define rREPe(i, n) rFORe((i), 1, (n))
#define rREPo(i, n) rFORe((i), 0, (n))
#define rep(i, n) FOR((i), 0, (n))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define dup(x, y) (((x)+(y)-1)/(y))
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using P = pair<int,int>;
using T = tuple<int,int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using vp = vector<P>;
using vt = vector<T>;

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

int main() {
  int n;
  cin >> n;
  vi a(n+1), b(n);
  REP(i, n+1) cin >> a[i];
  REP(i, n) cin >> b[i];
  ll ans = 0;
  REP(i, n) {
    int c = min(b[i], a[i]);
    int d = min(b[i]-c, a[i+1]);
    ans += (c+d);
    a[i+1] -= d;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<stdio.h>
using namespace std;
int main() {
	int ans=0;
	char ch;
	while (true) {
		while ((ch = getchar()) != '\n') {
			ans += ch - '0';
		}
		if (ans == 0) {
			break;
		}
		else {
			cout << ans << endl;
			ans = 0;
		}
	}
}


Measured memory_bytes: 3084
/*=============================================================================================================================/*
                                               Bismillahir Rahmanir Rahim

      _     ____  ___  ____   _   _  _         ___  ____   _         _     __  __
     / \   / ___||_ _|| __ ) | | | || |       |_ _|/ ___| | |       / \   |  \/  |
    / _ \  \___ \ | | |  _ \ | | | || |        | | \___ \ | |      / _ \  | |\/| |
   / ___ \  ___) || | | |_) || |_| || |___     | |  ___) || |___  / ___ \ | |  | |
  /_/   \_\|____/|___||____/  \___/ |_____|   |___||____/ |_____|/_/   \_\|_|  |_|

   _   __           __  __  __
  |_) (_  _  o__   /   (_  |_
  |_)o__)(_  || |  \__ __) |__

    ___                    _   _      _                _ _               __   ___                 _         _        _
   / __|_ _ ___ ___ _ _   | | | |_ _ (_)_ _____ _ _ __(_) |_ _  _   ___ / _| | _ ) __ _ _ _  __ _| |__ _ __| |___ __| |_
  | (_ | '_/ -_) -_) ' \  | |_| | ' \| \ V / -_) '_(_-< |  _| || | / _ \  _| | _ \/ _` | ' \/ _` | / _` / _` / -_|_-< ' \
   \___|_| \___\___|_||_|  \___/|_||_|_|\_/\___|_| /__/_|\__|\_, | \___/_|   |___/\__,_|_||_\__, |_\__,_\__,_\___/__/_||_|
                                                            |__/                           |___/


   FB: https://facebook.com/SIAsibul
   Gmail: asibulislam8@gmail.com

/*=============================================================================================================================*/

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

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef vector<pii> vii;
typedef vector<pil> vil;
typedef vector<pli> vli;
typedef vector<pll> vll;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz size()
#define all(a)  a.begin(), a.end()
#define mem(a, b)     memset(a, b, sizeof(a))
#define f0(i,n) for(int i=0;i<(n);i++)
#define f1(i,n) for(int i=1;i<=(n);i++)
#define f2(i,a,n) for(int i=(a);i<=(n);i++)
#define fr(i,n,a) for(int i=(n);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))
#define nl "\n"


const int INF = 1e9 + 5;
const int MXN = 2e5 + 5;


int main(){
    string s;
    cin >> s;
    int ans;
    if(s == "SUN") ans = 7;
    else if(s == "MON") ans = 6;
    else if(s == "TUE") ans = 5;
    else if(s == "WED") ans = 4;
    else if(s == "THU") ans = 3;
    else if(s == "FRI") ans = 2;
    else if(s == "SAT") ans = 1;
    cout << ans << nl;
    return 0;
}


Measured memory_bytes: 3568
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int count= 0;
        for(int i = a; i <= b; i++){
            if(c%i == 0){
                count++;
            }
        }
        System.out.println(count);
    }
}


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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
const ld eps = 1e-9;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template <typename T1, typename T2>
void chmax(T1 &a, const T2 &b) {
  if(a < b) a = b;
}

template <typename T1, typename T2>
void chmin(T1 &a, const T2 &b) {
  if(a > b) a = b;
}

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

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

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

  double r; cin >> r;

  cout << 2 * acos(-1) * r << endl;
  
}


Measured memory_bytes: 3800
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

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

	int N;
	cin >> N;

	int dp[N + 1];
	rep(i, 0, N + 1) dp[i] = 1e9;

	rep(i, 0, 6) dp[i] = i;


	rep(i, 6, N + 1) {
		rep(j, 0, 5) if(i - j >= 0) dp[i] = min(dp[i], dp[i - j] + j);
		for(int j = 1; pow(9, j) <= N; j++) {
			int idx = i - pow(9, j);
			if(idx >= 0) {
				dp[i] = min(dp[i], dp[idx] + 1);
			}
		}
		for(int j = 1; pow(6, j) <= N; j++) {
			int idx = i - pow(6, j);
			if(idx >= 0) {
				dp[i] = min(dp[i], dp[idx] + 1);
			}
		}
	}

	cout << dp[N] << endl;
}


Measured memory_bytes: 640
N, C, K = map(int, input().split())
Ts = [int(input()) for _ in range(N)] + [10 ** 10]

Ts.sort()

num = 1
limT = Ts[0] + K
ans = 0
for T in Ts[1:]:
    if limT < T or num == C:
        # バス出発
        num = 1
        limT = T + K
        ans += 1
    else:
        num += 1

print(ans)


Measured memory_bytes: 7872
#include <bits/stdc++.h>
#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
    #include <filesystem>
    namespace fs = std::filesystem;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
static mt19937 _g(time(nullptr));
 
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

string s,t;
void input(){
    fast_io();
    #ifdef __LOCAL
        fs::path __p = __FILE__;
        fs::path __input, __output;
        __input = __output = __p.parent_path();
        __input += string("/input/") + string(__p.stem()) + string(".txt");
        __output += string("/output/") + string(__p.stem()) + string(".txt");
        freopen(__input.c_str(), "r", stdin);
        freopen(__output.c_str(), "w", stdout);
    #endif
    cin >> s >> t;
}

bool isMatch(string a, string t){
    if(a.length()<t.length()) return false;
    for (int i = 0; i < t.length(); i++)
    {
        if(a[i]==t[i] || a[i]=='?') continue;
        else return false;
    }
    return true;
}

void change(string &a){
    for (int i = 0; i < a.length(); i++)
    {
        if(a[i]=='?') a[i]='a';
    }
    
}

int solve(){
    for (int i = s.length()-1; i >= 0; i--)
    {
        if(isMatch(s.substr(i),t)){
            DBG(i)
            string x = s.substr(0,i)+t+s.substr(i+t.length());
            s = x;
            break;
        }
        if(i==0){
            cout << "UNRESTORABLE" << endl;
            return 0;
        }
    }
    DBG(s)
    change(s);
    cout << s << endl;
    return 0;
}   

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


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main()
{
	int num[32];

	num[0] = 1;
	num[1] = 1;
	num[2] = 1;
	num[3] = 2;
	num[4] = 1; 
	num[5] = 2;
	num[6] = 1;
	num[7] = 5;
	num[8] = 2;
	num[9] = 2;
	num[10] = 1;
	num[11] = 5;
	num[12] = 1;
	num[13] = 2;
	num[14] = 1;
	num[15] = 14;
	num[16] = 1;
	num[17] = 5;
	num[18] = 1;
	num[19] = 5;
	num[20] = 2;
	num[21] = 2;
	num[22] = 1;
	num[23] = 15;
	num[24] = 2;
	num[25] = 2;
	num[26] = 5;
	num[27] = 4;
	num[28] = 1;
	num[29] = 4;
	num[30] = 1;
	num[31] = 51;
			

	int k;
	cin >> k;
	cout << num[k - 1] << "\n";
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()) {
			int num = scanner.nextInt();
			int pair = 0;
			for(int i = 1; i <= num; i++) {
				if (isPrime(i) && isPrime(num-i+1)) {
					pair++;
				}
			}
			System.out.println(pair);
		}
	}

	private static boolean isPrime(int n) {
		if (n == 1) return false;
		if (n == 2) return true;
		if (n % 2 == 0) return false;
		
		for(int i = 3; i <= Math.sqrt(n); i += 2) {
			if (n % i == 0) return false;
		}
		return true;
	}
}

Measured memory_bytes: 23580
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <bitset>

long long mod = 1e9+7;
class Mint {
public:
  long long x;
  Mint(){}; // 引数なしでも定義できるように引数なしコンストラクタも用意しておく
  Mint(long long a){
    x = a%mod;
    while(x<0){
      x += mod;
    }
  };
  Mint& operator += (const Mint &a){
    x+=a.x;
    x%=mod;
    return *this;
  }
  Mint& operator -= (const Mint &a){
    x += (mod - a.x);
    x%=mod;
    return *this;
  }
  Mint& operator *= (const Mint &a){
    x*=a.x;
    x%=mod;
    return *this;
  }

  // a^n mod を計算する
  // Useaeg: Mint z = y.pow(y, n);
  Mint pow(Mint a, long long n) const {
    Mint y(1);
    Mint b(a);
    while (n > 0) {
      if (n & 1) y *= b;
      b *= b;
      n >>= 1;
    }
    return y;
  }

  // a^{-1} mod を計算する
  Mint modinv(const Mint &a) const {
    return pow(a, mod-2);
  }

  Mint& operator /= (const Mint &a) {
    x *= modinv(a).x;
    x %= mod;
    return *this;
  }

  Mint operator + (Mint &a) const {
    Mint y(*this);
    y += a;
    return y;
  }

  Mint operator - (Mint &a) const {
    Mint y(*this);
    y -= a;
    return y;
  }

  Mint operator * (Mint &a) const {
    Mint y(*this);
    y *= a;
    return y;
  }

  Mint operator / (Mint &a) const {
    Mint y(*this);
    y/=a;
    return y.x;
  }

  // nCk @mod を計算する
  Mint nCk(Mint &n, const long long k) const {
    Mint y = Mint(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
      y /= i;
    }
    return y;
  }

  // nPk @mod を計算する
  Mint nPk(Mint &n, long long k) const {
    Mint y(1);
    for (Mint i(0); (i.x)<k; i.x++){
      y *= (n-i);
    }
    return y;
  }
};

struct node {
  int v;
  int supply;
  int amari;
};

class MyComparison {
public:
  bool operator()(node n1, node n2) {
    return (n1.supply!=n2.supply)?(n1.supply>n2.supply):(n1.amari<n2.amari);
  }
};

std::bitset<26000> dp1[84];
std::bitset<26000> dp2[84];
int A[84][84];
int B[84][84];
int main(){
  int H, W;
  std::cin >> H >> W;
  for (int i=0; i<H; i++) {
    for (int j=0; j<W; j++) {
      std::cin >> A[i][j];
    }
  }
  for (int i=0; i<H; i++) {
    for (int j=0; j<W; j++) {
      std::cin >> B[i][j];
    }
  }
  int MAX = 26000;

  int offset = MAX/2;
  dp2[0][+A[0][0]-B[0][0]+offset] = true;
  dp2[0][-A[0][0]+B[0][0]+offset] = true;
  for (int i=0; i<H; i++) {
    //printf("i=%d\n", i);
    for (int j=0; j<W; j++) {
      if (i>0) {
        dp2[j] |= dp1[j]<<abs(A[i][j]-B[i][j]);
        dp2[j] |= dp1[j]>>abs(A[i][j]-B[i][j]);
      }
      if (j>0) {
        dp2[j] |= dp2[j-1]<<abs(A[i][j]-B[i][j]);
        dp2[j] |= dp2[j-1]>>abs(A[i][j]-B[i][j]);
      }
    }

    for (int j=0; j<W; j++) {
      dp1[j] = 0;
    }
    
    std::swap(dp1, dp2);
    //printf("dp1[1][550000] = %d\n", dp1[1][550000]);
  }
  int ans = 1001001001;
  for (int k=0; k<MAX; k++) {
    if (dp1[W-1][k]){
      //printf("dp1[%d][%d] seleced\n", W-1, k);
      ans = std::min(ans, abs(k-offset));
    }
  }
  std::cout << ans << std::endl;
  return 0;
}

Measured memory_bytes: 3788
o = list(str(input()))
e = list(str(input()))

l = len(o)+len(e)+1
r = ''
o_count = 0
e_count = 0
for i in range(1, l):
  if i % 2 == 0:
    r += e[i - (2 + o_count)]
    o_count += 1
  else:
    r += o[i - (1 + e_count)]
    e_count += 1

print(r)

Measured memory_bytes: 3060
#!/usr/bin/ruby
# -*- coding: utf-8 -*-
class Main
  def initialize()
    #fh = open("x.txt")
    fh = STDIN
    n = fh.gets.chomp.to_i
    count=0
    fl = fh.gets.chomp.split.map{|x| x.to_i}
    abort if fl.length != n

    ans = insertion(fl)
    n = ans.shift
    puts ans.map{|x|x.to_s}.join(" ")
    puts n
  end

  def insertion(a)
    n = 0
    0.upto(a.length-1).each{|i|
      mini = i
      i.upto(a.length-1).each{|j|
        if a[j] < a[mini] then
          mini = j
        end
      }
      if i != mini then
        tmp = a[i]
        a[i] = a[mini]
        a[mini] = tmp
        n += 1
      end
    }
    a.unshift(n)
  end
end

if $0==__FILE__ then
  Main.new()
end

Measured memory_bytes: 8648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll x, a, b;
a = 1;
  in(x);
  rep2(i, 2, 32){
    b = i;
    while(b * i <= x){
      b = b * i;
      a = max(a, b);
    }
  }
  out(a);
  memi;
}

Measured memory_bytes: 256
h,w = map(int,input().split())
ans = []
if h%3 == 0 or w%3 == 0:
	print('0')
else:
	a = h
	s = []
	if a%2 == 0:
		d = a/2
		if w%3 == 1:
			b = (w-1)/3
			c = w - b
			s.append(a*b)
			s.append(c*d)
		else:
			b = (w+1)/3
			c = w-b
			s.append(a*b)
			s.append(c*d)
	else:
		d = (a-1)/2
		if w%3 == 1:
			b = (w-1)/3
			c = w - b
			s.append(a*b)
			s.append(c*d)
			s.append(c*(d+1))
		else:
			b = (w+1)/3
			c = w-b
			s.append(a*b)
			s.append(c*d)
			s.append(c*(d+1))
	ans.append(abs(int(max(s)-min(s))))
	x = w
	w = h
	h = x
	if h%3 == 0 or w%3 == 0:
		print('0')
	else:
		a = h
		k = []
		if a%2 == 0:
			d = a/2
			if w%3 == 1:
				b = (w-1)/3
				c = w - b
				k.append(a*b)
				k.append(c*d)
			else:
				b = (w+1)/3
				c = w-b
				k.append(a*b)
				k.append(c*d)
		else:
			d = (a-1)/2
			if w%3 == 1:
				b = (w-1)/3
				c = w - b
				k.append(a*b)
				k.append(c*d)
				k.append(c*(d+1))
			else:
				b = (w+1)/3
				c = w-b
				k.append(a*b)
				k.append(c*d)
				k.append(c*(d+1))
		ans.append(abs(int(max(k)-min(k))))
	ans.append(h)
	ans.append(w)
	print(min(ans))

Measured memory_bytes: 3192
#include<iostream>
#include <algorithm>
#include <cmath>

using namespace std;
int memo[1000001] = {0};
int mod = pow(10, 9) + 7;

int saiki(int s){
    if(memo[s] != -1){return memo[s];}
    if(s == 0){return 1;}
    int ans = (saiki(s-1) + saiki(s-2))%mod;
    memo[s] = ans;
    return ans;
}
int main(){
    int n, m;
    cin >> n >> m;
    for(int l = 0; l <1000001; l++){
        memo[l] = -1;
    }
    for(int i=0;i<m;i++){
        int o;cin >> o;
        memo[o] = 0;
    }
    cout << saiki(n) << endl;
}

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

int main(){
  int a[3][3];
  int hantei[3][3];
  for (int i=0;i<3;i++){
    for (int j=0;j<3;j++){
      cin>>a[i][j];
    }
  }
  for (int i=0;i<3;i++){
    for (int j=0;j<3;j++){
      hantei[i][j]=0;
    }
  }
  int N;
  cin >> N;
  int b[N];
  for (int k=0;k<N;k++){
    cin>>b[k];
    for (int i=0;i<3;i++){
      for (int j=0;j<3;j++){
        if(a[i][j]==b[k]){
          hantei[i][j]=1;
        }
      }
    }
  }
  for (int i=0;i<3;i++){
    if(hantei[i][0]+hantei[i][1]+hantei[i][2]==3){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
 for (int i=0;i<3;i++){
    if(hantei[0][i]+hantei[1][i]+hantei[2][i]==3){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  if(hantei[0][0]+hantei[1][1]+hantei[2][2]==3){
          cout<<"Yes"<<endl;
      return 0;
    }
    if(hantei[0][2]+hantei[1][1]+hantei[2][0]==3){
          cout<<"Yes"<<endl;
      return 0;
    }
    
  cout<<"No"<<endl;
  return 0;
}


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

using namespace std;

typedef vector <int> VI;
typedef vector <VI> VVI;

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

int w, h;
int sx, sy, gx, gy;
VVI M;
int answer;

//==================================================
// Tõ
//==================================================
void dfs( int x, int y, int a, int d )
{
	if ( d > 10 ) return;

	if ( M[y][x] == 3 )
	{
		if ( answer == -1 )
			answer = d;
		else
			answer = min( answer, d );
	}
	if ( a > 0 )
	{
		int nx = x + dx[a];
		int ny = y + dy[a];
		if ( nx < 0 || nx >= w || ny < 0 || ny >= h )
			return;
		if ( M[ny][nx] == 1 )
		{
			M[ny][nx] = 0;
			dfs( x, y, 0, d );
			M[ny][nx] = 1;
		}
		else
			dfs( nx, ny, a, d );
	}
	else
	{
		for ( int i = 1; i < 5; i++ )
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if ( nx < 0 || nx >= w || ny < 0 || ny >= h )
				continue;
			if ( M[ny][nx] == 0 || M[ny][nx] == 3 )
			{
				dfs( nx, ny, i, d+1 );
			}
		}
	}

}

int main( void )
{
	while ( cin >> w >> h && w && h )
	{
		//==================================================
		// Ï
		//==================================================
		M = VVI( h, VI( w, 0 ) );
		answer = -1;

		//==================================================
		// }bvÌüÍ
		//==================================================
		for ( int i = 0; i < h; i++ )
		{
			for ( int j = 0; j < w; j++ )
			{
				int& s = M[i][j];
				cin >> s;

				// X^[gES[
				if ( s == 2 )
				{
					sx = j;
					sy = i;
					s  = 0;
				}
				else if ( s == 3 )
				{
					gx = j;
					gy = i;
				}
			}
		}

		//==================================================
		// 
		//==================================================
		dfs( sx, sy, 0, 0 );

		//==================================================
		// oÍ
		//==================================================
		cout << answer << endl;
	}
	return 0;
}

Measured memory_bytes: 916
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
template<class T> using VE = vector<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
const int N = 202020;
V a(N);
VV g(N);
V dp(N, upper);
V ans(N);
VE<bool> visited(N, false);
stack<P<int>> prevpos;
void dfs(int x) {
	visited[x] = true;
	auto itr = lower_bound(all(dp), a[x]);
	int pos = itr - dp.begin();
	prevpos.push(make_pair(pos, *itr));
	dp[pos] = a[x];
	int res = lower_bound(all(dp), upper) - dp.begin();
	ans[x] = res;
	for (auto c : g[x]) {
		if (!visited[c]) dfs(c);
	}
	int p = prevpos.top().first;
	int num = prevpos.top().second;
	prevpos.pop();
	dp[p] = num;
}
int main() { //dfsしながら巻き戻すことで配列一個でできる,巻き戻すっていう発想が凄い
	int n;
	cin >> n;
	rep(i, n) {
		cin >> a[i];
	}
	rep(i, n - 1) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		g[x].push_back(y); g[y].push_back(x);
	}
	dfs(0);
	rep(i, n) cout << ans[i] << endl;
	return 0;
}

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



int main(){
    ll n,m;cin>>n>>m;
    if(n==0||m==1){
        cout<<0<<endl;
        return 0;
    }
    
    ll an=n%m;
    cout<<(ll)min(an,m-an)<<endl;
}
    









Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
vector<int>v, a, b, c;
int32_t main()
{
    ios_base::sync_with_stdio(0);
    int ans = 0, n = 0;
    cin >> n;

    int r = 1;
    for(int i = 1; v.size() <= 9; i++){
        v.pb(3);
        a = v;
        for(int j = i+1; v.size() <= 9; j++){
            v.pb(5);
            b = v;

            for(int k = j+1; v.size() <= 9; k++){
                v.pb(7);
                sort(v.begin(), v.end());
//                for(int ok = 0; ok < v.size(); ok++){
//                    cout << v[ok] <<" ";
//                }
//                cout << endl;

                do{
                    int rr = v[0];
                    for(int p = 1; p < v.size(); p++){
                        rr *= 10;
                        rr += v[p];
                    }
                    if(rr <= n){
                        ++ans;
                       // cout << rr << endl;
                    }
                    else{
                        break;
                    }


                }
                while(next_permutation(v.begin(), v.end()));

            }
            v = b;
        }
        v = a;
    }
    cout << ans;
}


Measured memory_bytes: 256
#define MYDEBUG
#include <bits/stdc++.h>
#ifdef MYDEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#define ifcin(x) std::ifstream cin(x)
#else
#define debug(x)
#define ifcin(x)
#endif
#define ll long long
#define ull unsigned long long
#define eps 1e-14
#define all(x) x.begin(), x.end()
#define rep(i,from,to) for(int i=from; i<to; ++i)
#define REP(i,from,to) for(int i=from; i<=to; ++i)
using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::ostream;
using std::swap;
using std::max;
using std::min;
using std::queue;
typedef struct edge edge;
typedef struct unionFind unionFind;
typedef struct Graph Graph;

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  size_t last = v.size() - 1;
  for (size_t i = 0; i < v.size(); ++i) {
    out << v[i];
    if (i != last)
      out << ",";
  }
  out << "]";
  return out;
}

struct unionFind{
	vector<int> par;
	vector<int> rank;
	unionFind(int n) : par(n), rank(n,1) {
		rep(i,0,n){
			par[i] = i;
		}
	}
	
	int find(int x){
		if(par[x] == x){
			return x;
		}
		return par[x] = find(par[x]);
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
	
	void unite(int x, int y){//rank[x] > rank[y]
		x = find(x);
		y = find(y);
		if(x == y){
			return;
		}
		if(rank[x] < rank[y]){
			swap(x,y);
		}
		par[y] = x;
		rank[x] += rank[y];
		rank[y] = 0;
	}
	
	int size(int x){
		return rank[x];
	}
};

struct edge{
	int from, to, cost;
	edge(int from, int to, int cost){
		this->from = from;
		this->to = to;
		this->cost = cost;
	}
	
	edge(){
		*this = edge(-1,-1,-1);
	}
	
	bool operator<(const edge& e) const{
		return cost < e.cost;
	}
};

class Graph{
	public:
	static int kruskal(vector<edge>& es){
		sort(all(es));
		unionFind uf(es.size());
		int min_cost = 0;
		rep(i,0,es.size()){
			edge& e = es[i];
			if(!uf.same(e.from, e.to)){
				min_cost += e.cost;
				uf.unite(e.from, e.to);
			}
		}
		return min_cost;
	}
};


int V,E;
void solve(){
	ifcin("/storage/emulated/0/AppProjects/past15/jni/in.txt");
	cin >> V >> E;
	vector<edge> es;
	rep(i,0,E){
		int s,t,d;
		cin >> s >> t >> d;;
		es.push_back(edge(s,t,d));
	}
	cout << Graph::kruskal(es) << endl;
}

void uftest(){
	//ifcin("/storage/emulated/0/AppProjects/past15/jni/in.txt");
	int n,q;
	cin >> n >> q;
	unionFind uf(n);
	rep(i,0,q){
		int com,x,y;
		cin >> com >> x >> y;
		if(com==0){
			uf.unite(x,y);
		}else{
			cout << uf.same(x,y) << endl;
		}
	}
}

int main() {
	//solve();
	uftest();
}

Measured memory_bytes: 3188
# -*- coding: utf-8 -*-

N = int(input())

L0 = 2
L1 = 1

if N == 1:
    print(1)
    exit()

for i in range(2, 87):

    Li = L1 + L0
    if N == i:
        print(Li)
        exit()
    else:
        L0 = L1
        L1 = Li

Measured memory_bytes: 3060
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
#define A first
#define B second
#define pb push_back
void chmax(int &a, int b) { a = (a > b ? a : b); }
void chmin(int &a, int b) { a = (a < b ? a : b); }
const int f[] = {2,5,5,4,5,6,3,7,6};
vector<int> ans;

void getpre(int p, vector<int> &pre) {
    if(pre[p] == -1) return ;
   // cout << "NOE " << p  << " , " << pre[p]<< endl; getchar();
    getpre(p - f[pre[p] - 1], pre);
    ans.pb(pre[p]);
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(M);
    for(int i = 0;i < M;i++) cin >> A[i];
    sort(A.begin(), A.end());
    
    vector<pii> dp(N+1, pii(0,0));
    vector<int> pre(N+1);
    dp[0] = pii(1, 0); pre[0] = -1;
    for(int i = 1;i <= N;i++) {
        int mi = -1, mj;
        for(int j = M - 1;j >= 0;j--) {
            int k = f[A[j] - 1];
            if(k > i) continue;
            if(!dp[i - k].A) continue;
            else {
                if(mi == -1 || dp[mi].B < dp[i - k].B) {
                    mi = i - k;
                    mj = j;
                }
            }
        }
        if(mi != -1) {
            dp[i] = pii(1, dp[mi].B + 1);
            pre[i] = A[mj];
        }
    }
    
    getpre(N, pre);
    sort(ans.begin(), ans.end());
    for(int i = ans.size() - 1;i >= 0;i --) {
        cout << ans[i];
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
signed main(){
    int n;cin >> n;
    int a[n];
    vector<int> ans(n);
    rep(i,n)cin >> a[i];
    rep(keta,30){
        vector<int> tmp(n,0);
        int ret = 0;
        rep(i,n){
            if(a[i]>>keta&1){
                tmp[i] = 1;
                ret++;
            }

        }
        rep(i,n){
            if(ret%2 == 1)ans[i] |= (tmp[i]^1)<<keta;
            else ans[i] |= (tmp[i])<<keta;
        }
    }
    rep(i,n)cout << ans[i] << endl;


    return 0;
}

Measured memory_bytes: 7892
#ifdef _WIN32
#include "stdc++.h"
#else
#include <bits/stdc++.h>
#endif

// 継承可能な型
template <class Type>
struct IN : Type
{
	IN()
	{
		std::cin >> *this;
	}
};

// 継承不可能な型
template <class Type>
struct IN_
{
	Type val;

	IN_()
	{
		std::cin >> val;
	}

	operator Type&()
	{
		return val;
	}

	IN_<Type>& operator=(const Type& _value)
	{
		val = _value;
		return *this;
	}
};

template <class Char, class Type>
std::basic_ostream<Char>& operator <<(std::basic_ostream<Char>& os, const IN_<Type>& value)
{
	return os << value.val;
}

template <class Char, class Type>
std::basic_istream<Char>& operator >>(std::basic_istream<Char>& is, IN_<Type>& value)
{
	return is >> value.val;
}

template <class Type>
void OUT(const Type& value)
{
	std::cout << value << std::endl;
}

template <class Type, class ... Args>
void OUT(const Type& value, const Args& ... args)
{
	std::cout << value << ' ';
	OUT(args...);
}

void YES()
{
	OUT("YES");
}
void NO()
{
	OUT("NO");
}
void YESNO(const bool cond)
{
	OUT(cond ? "YES" : "NO");
}

void Yes()
{
	OUT("Yes");
}
void No()
{
	OUT("No");
}
void YesNo(const bool cond)
{
	OUT(cond ? "Yes" : "No");
}

using ll = long long;
using inll = IN_<ll>;
using vll = std::vector<ll>;
using setll = std::set<ll>;
using msetll = std::multiset<ll>;
using instr = IN<std::string>;

// 階乗を計算 O(N) (N=10^7 で O(10^7))
ll factorial(ll n)
{
	for (ll i = n - 1; i > 1; --i)
		n *= i;
	return n;
}

// nCrを計算 O(N) (N=10^7 で O(10^7))
ll ncr(const ll n, ll r)
{
	if (r * 2 > n) r = n - r;

	ll dividend = 1, divisor = 1;

	for (ll i = 1; i <= r; ++i) {
		dividend *= n - i + 1;
		divisor *= i;
	}

	return dividend / divisor;
}

// 素数判定 O(sqrt(N)) (N=10^7 で O(10^3))
bool isprime(const ll num)
{
    if (num < 2) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (ll i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0) return false;
    }

    return true;
}

// 各桁の和を計算 O(logN) (N=10^7 で O(7))
ll digsum(ll n)
{
	ll sum = 0;
	while(n != 0){
		sum += n % 10;
		n /= 10;
	}
	return sum;
}

#define FOR(i, m, n) for (ll (i) = (m); (i) < (n); ++(i))
#define REP(i, n) for (ll (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for (ll (i) = (n); (i) >= 0; --(i))
#define ITRREP(it, v) for (auto (it) = (v).begin(); (it) != (v).end(); ++(it))
#define ITRREPR(it, v) for (auto (it) = (v).rbegin(); (it) != (v).rend(); ++(it))
#define DIVUP(a, b) (((a) + (b) - 1) / (b))

void Main();

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

	Main();

#ifdef _DEBUG
	system("pause");
#endif

	return 0;
}

using namespace std;

//////////////////////////////

void Main()
{
	instr a;
	for (auto b : a)
	{
		if (b == '1') cout << 9;
		else if (b == '9') cout << 1;
		else cout << b;
	}

	cout << endl;
	return;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>

using namespace std;

int main()
{
  int N, W;
  scanf("%d%d", &N, &W);
  
  int w[105];
  int v[105];
  for (int i = 0; i < N; i++)
    scanf("%d%d", &w[i], &v[i]);
  
  long long dp[105][100005] = {};
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= W; j++)
      dp[i+1][j] = dp[i][j];
    for (int j = 0; j <= W; j++) {
      if (j+w[i] <= W)
        dp[i+1][j+w[i]] = max(dp[i+1][j+w[i]], dp[i][j]+v[i]);
    }
  }
  
  printf("%lld\n", dp[N][W]);
  
  return 0;
}

Measured memory_bytes: 82176
#include <bits/stdc++.h>
using namespace std;
const int limit = 50;

int n, m;
int a[limit], b[limit];
bool g[limit][limit];
bool visited[limit];

void dfs(int v) {
	visited[v] = true;
	for (int v2 = 0; v2 < n; v2++) {
		if (g[v][v2] == false) continue;
		if (visited[v2] == true) continue;
		dfs(v2);
	}
}

int main(void) {
	cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        g[a[i]][b[i]] = g[b[i]][a[i]] = true;
    }
    
    int ans = 0;
    for(int i=0; i<m; i++){
        g[a[i]][b[i]] = g[b[i]][a[i]] = false;
        for(int j=0; j<n; j++) visited[j] = false;
	    dfs(0);
        
        bool bridge = false;
        for(int j=0; j<n; j++){
            if(visited[j] == false) bridge = true;
        }
		if (bridge) ans ++;
		g[a[i]][b[i]] = g[b[i]][a[i]] = true;
	}

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

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int N, T, A;
    cin >> N;
    cin >> T;
    cin >> A;
    int *H;
    H = new int[N];
    for(int i = 0; i < N; i++) cin >> H[i];
    
    float fDif = 10000;
    int nNum = 0;
    
    for(int i = 0; i < N; i++) {
        float Tb = T - H[i] * 0.006f;
        float fDifb = Tb - A > 0 ? Tb - A : A - Tb;
        if(fDifb < fDif) {
            fDif = fDifb;
            nNum = i + 1;
        }
    }
    
    cout << nNum << endl;
    return 0;
}

Measured memory_bytes: 256