akhauriyash/Code-Regression huggingface dataset:
def main():
    n = int(input())
    if n == 1:
        print(0)
        return
    def eratos(n):
        flag = [True] * (n + 1)
        for i in range(2, int(n**0.5) + 1):
            if flag[i]:
                for j in range(2*i, n + 1, i):
                    flag[j] = False
        return [i for i, x in enumerate(flag) if x and i >= 2]
    p = eratos(10**6)
    work = []
    for i in p:
        piyo = 0
        while n % i == 0:
            n //= i
            piyo += 1
        if piyo > 0:
            work.append(piyo)
        if n == 1:
            break
    if len(work) == 0:
        print(1)
        return
    else:
        result = 0
        for i in work:
            for j in range(1, 10**6):
                i -= j
                if i <0:
                    break
                result += 1
    if n != 1:
        result += 1
    print(result)
main()

Measured memory_bytes: 20344
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;

namespace b
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var t = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();            
            var m = int.Parse(Console.ReadLine());

            BigInteger sum = t.Sum();
            for(var i = 0; i < m; i++){
                var _ = Console.ReadLine().Split();
                var p = int.Parse(_[0]);
                var x = int.Parse(_[1]);

                Console.WriteLine(sum - t[p-1] + x);
            }
        }
    }
}


Measured memory_bytes: 13652
fn main() {
    let k = read().parse::<usize>().unwrap();
    let mut second_line = read_as_vec().into_iter().map(|s| s.parse::<usize>().unwrap());
    let a = second_line.next().unwrap();
    let b = second_line.next().unwrap();
    for i in a..b + 1 {
        if i % k == 0 {
            println!("OK");
            return;
        }
    }
    println!("NG");
}
fn read() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}
fn read_as_vec() -> std::vec::Vec<String> {
    read().split(' ').map(|s| s.to_string()).collect()
}

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

int main() {
  int a, b;
  double t;
  cin >> a >> b >> t;
  
  int time = 1; //回数を数える
  int count = 0;  //クッキーの数を代入
  while(t + 0.5  > a * time){
    count += b;
    time++;
  }
  cout << count <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define inf 999999999
#define loop(i, a, b) for (int i = (a), i##len = (b); i < i##len; ++i)
#define rep(i, n) loop(i, 0, n)
#define lin long long
#define lfl long double

long dp1[2020];
long dp2[2020];

int main(void)
{
    string s;
    cin >> s;
    long res = 0;

    for (int i = 0; i < s.length(); i++)
    {
        int dig = s[i] - '0';

        for (int j = 0; j < 2019; j++)
        {
            int ni = (j * 10 + dig) % 2019;
            dp2[ni] += dp1[j];
        }

        dp2[dig]++;
        res += dp2[0];
        //cout << dp2[1] << endl;

        for (int j = 0; j < 2019; j++)
        {
            dp1[j] = dp2[j];
            dp2[j] = 0;
        }

    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 3720
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize, w: usize,
        goods: [(usize, usize); n]
    }
    const V: usize = 100000;
    let mut dp = vec![1 << 60; V + 1];
    dp[0] = 0;

    for &(weight, value) in &goods {
        for i in (value..V + 1).rev() {
            dp[i] = std::cmp::min(dp[i], dp[i - value] + weight);
        }
    }
    for i in (0..V + 1).rev() {
        if dp[i] <= w {
            println!("{}", i);
            break;
        }
    }
}


Measured memory_bytes: 4352
import math

def isPrime(x):
  if x == 1: return False
  
  for k in range(2, int(math.sqrt(x) + 1)):
    if x % k == 0:
      return False
  return True

n = int(input())

while True:
  if isPrime(n):
    print(n)
    break
  n += 1

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;
int N,M;
ll dp[100001];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>N>>M;
    set<int> s;
    rep(i,0,M){
        int a;
        cin>>a;
        s.insert(a);
    }
    dp[0]=1;
    if(s.count(1)) dp[1]=0;
    else{
        dp[1]=1;
    }
    rep(i,2,N+1){
        if(s.count(i)) dp[i]=0;
        else{
            dp[i]=dp[i-1]+dp[i-2];
            dp[i]%=MOD;
        }
    }
    cout <<dp[N]<<"\n";
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size();
    vector<char> table(26);
    rep(i, 26) table[i] = 'a' + i;
    rep(i, n) {
        char from = table[s[i] - 'a'];
        char to = t[i];

        auto it_f = find(table.begin(), table.end(), from);
        auto it_t = find(table.begin(), table.end(), to);

        *it_f = to;
        *it_t = from;

    }

    rep(i, n) {
        char from = s[i];
        char to = table[from - 'a'];
        if (t[i] == to)continue;
        cout << "No" << endl;
        ret();
    }
    cout << "Yes" << endl;

}


Measured memory_bytes: 3904
#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
#define pb(X) push_back(X)
#define x first
#define y second
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
using namespace std;

typedef pair<int, int> pii;
 
int n, a, b, c, d, q, ans;
 
int main() {
	INIT
	int k;
	cin >> n >> k;
	string s;
	cin >> s;
	int i = 0;
	int j = 0;
	while (j < n) {
		while (s[j] == '1' && j < n) ++j;
		ans = max(ans, j - i);
		while (s[j] == '0' && j < n) ++j;
		--k;
		if (k < 0) {
			while (s[i] == '1' && i < n) ++i;
			while (s[i] == '0' && i < n) ++i;
		}
		ans = max(ans, j - i);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;

const ll INF = 1ll << 60;

int main()
{
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    reverse(ALL(s));
    int cur = 0;
    vector<int> ans;
    while (cur != n)
    {
        //cerr << cur << endl;
        bool change = false;
        for (int i = m; i >= 1; i--)
        {
            if (cur + i <= n && s[cur + i] == '0')
            {
                cur += i;
                change = true;
                ans.push_back(i);
                break;
            }
        }
        if (change == false)
        {
            cout << -1 << endl;
            return 0;
        }
    }
    cerr << ans.size() << endl;
    reverse(ALL(ans));
    for (auto x : ans)
    {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

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

public class Main {

	public static void main(String[] args){
	      Scanner sc = new Scanner(System.in);
	      int N = sc.nextInt();
	      int X  = sc.nextInt();
	      int[] m = new int[N];
	      for(int i = 0; i < N; i++) {
	    	  	m[i] = sc.nextInt();
	      }
	      sc.close();
	      
	      int count = 0;
	      
	      for(int i = 0; i < N; i++) {
	    	  	X -= m[i];
	    	  	count++;
	      }
	      
	      Arrays.sort(m);
	      count += X / m[0];
	      
	      System.out.println(count);
	      System.exit(0);
	    }

}

Measured memory_bytes: 23764
#! -*- coding:utf-8 -*-
def replace(num1,num2,nums):
    tmp = nums[num1-1]
    nums[num1-1]=nums[num2-1]
    nums[num2-1]=tmp

w = input()
nums = [x+1 for x in xrange(w)]
n = input()
for x in xrange(n):
    num1,num2 = map(int,raw_input().split(","))
    replace(num1,num2,nums)
for num in nums:
    print num

Measured memory_bytes: 6248
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<vector>
#include<complex>
using namespace std;

typedef complex< double > Pt;

int main(){
  int n;
  while(cin >> n, ~n){
    Pt now(1,0);
    double angle;
    for(int i = 1 ; i < n ; i++ ){
      angle = arg(now); //角度出したいね
      now.imag() += cos(angle);
      now.real() -= sin(angle);
    }
    cout << now.real() << " " << now.imag() << endl;
  }
}

Measured memory_bytes: 1328
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int a[200100];
int main()
{
	int k,n,out=0;
	cin>>k>>n;
	rep(i,n) cin>>a[i];a[n]=a[0]+k;
	rep(i,n) out=max(out,a[i+1]-a[i]);
	cout<<k-out<<endl;
}


Measured memory_bytes: 1152
fun main(args:Array<String>) {
    val (m,k) = readLine()!!.split(" ").map(String::toInt)
    if(m==1) {
        if(k==0) println("0 0 1 1")
        else println("-1")
    }
    else {
        if(k in 0 until (1 shl m)) {
            var ans = mutableListOf<Int>()    
            for(i in 0 until (1 shl m)) {
                if(i!=k) ans.add(i)
            }
            ans.add(k)
            for(i in (1 shl m)-1 downTo 0 ){
                if(i!=k) ans.add(i)
            }
            ans.add(k)
            println(ans.joinToString(separator=" "))

        }
        else {
            println("-1")
        }
    }
}

Measured memory_bytes: 62108
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <ctype.h>
#include <numeric>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1e9 + 7;
const int INF = 1e9;

int dx4[4] = { 0, -1, 1, 0 };
int dy4[4] = { -1, 0, 0, 1 };
int dx8[8] = { 0, -1, 1, 0, -1, 1, -1, 1 };
int dy8[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };

int main() {
  string s;
  cin >> s;

  cout << s[0];
  cout << s.size() - 2;
  cout << s[s.size() - 1] << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    long n,k;
    scanf("%ld %ld", &n, &k);
    vector<long> viP(n),viC(n);
    for(long i = 0; i < n; i++){
        scanf("%ld", &viP[i]);
        viP[i]--;
    }
    for(long i = 0; i < n; i++){        
        scanf("%ld", &viC[i]);
    }
    
    long nAns = -1000000000;
    for(long i = 0; i < n; i++){
        long j = i;
        long iLoopSum = 0;
        long nLoopCount = 0;
        while(true){
            iLoopSum += viC[viP[j]];
            j = viP[j];
            nLoopCount++;
            if(j == i){
                break;
            }
        }
        long iSum = 0;
        if(iLoopSum <= 0){
            for(long l = 0; l < nLoopCount; l++){
                iSum += viC[viP[j]];
                j = viP[j];                
                nAns = max(iSum, nAns);
            }
        } else {
            iSum = iLoopSum * (k/nLoopCount);
            long nRemain = k%nLoopCount;
            if(nRemain == 0){
                nRemain = nLoopCount;
                iSum -= iLoopSum;
            }
            nAns = max(iSum, nAns);
            for(long l = 0; l < nRemain; l++){
                iSum += viC[viP[j]];
                j = viP[j];                
                nAns = max(iSum, nAns);
            }
        }
    }
    
    printf("%ld", nAns);
    
    return 0;
}


Measured memory_bytes: 3308
def main():
    N = int(input())
    a = list(map(int, input().split()))
    count = 1
    ans = 0
    for i in range(N):
        if a[i] == count:
            count += 1
            continue
        else:
            ans += 1

    if count == 1 and ans != 0:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()


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

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

const long long INF = 1LL << 60;

int main() {
  int n, k;
  cin >> n >> k;
  long long h[100101];

  for (int i = 0; i < n; i++) cin >> h[i];

  long long dp[101000];
  for (int i = 0; i < 101000; i++) dp[i] = INF;
  dp[0] = 0;

  for (int i = 0; i < n; i++)
    for (int j = 1; j <= k; j++) {
      chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]));
  }
  cout << dp[n-1] << endl;
}

Measured memory_bytes: 1792
from statistics import median 
n = int(input())
a = list(map(int,input().split()))
ls = []
for i in range(n):
    ls.append(a[i] - i - 1)
b = median(ls)
if b % 1 == 0:
    ans = 0
    b = int(b)
    for i in range(n):
        ans += abs(a[i] - (b + i + 1))
    print(ans)
else:
    bigans = smallans = 0
    for i in range(n):
        bigans += abs(a[i] - (int(b) + i + 2))
        smallans += abs(a[i] - (int(b) + i + 1))
    print(min(bigans,smallans))

Measured memory_bytes: 27252
#include <bits/stdc++.h>
#include <fstream>
#include <string>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define ll long long

int main() {

    //入力
    int n,d;

    cin >> n >> d;
    vector<int> x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];

    //
    int ans = 0;
    rep(i, n) {
        if (sqrt((double)x[i] * x[i] + (double)y[i] * y[i]) <= d)
            ++ans;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4796
#include<bits/stdc++.h>
#define N 1000006 
using namespace std;
int f[N][2],n;
char s[N];
int main()
{
	f[0][1]=1;
	scanf("%s",s+1);
	n=strlen(s+1);
	for (int i=1;i<=n;i++)
	f[i][0]=min(f[i-1][0]+(s[i]^48),f[i-1][1]+10-(s[i]^48)),
	f[i][1]=min(f[i-1][0]+(s[i]^48)+1,f[i-1][1]+9-(s[i]^48));
	printf("%d\n",min(f[n][0],f[n][1]+1));
 } 

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


int main() {
  int D, N;
  cin >> D >> N;
  int ans = 1;
  for (int i = 0; i < D; i++) {
	  ans *= 100;
	}
  if (N == 100) {
	  N++;
	}
  cout << ans * N << endl;
  return 0;
}


Measured memory_bytes: 256
from collections import deque

def main():
    n, m = map(int, input().split())
    g = [[] for i in [0]*(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    def bfs(n, m, adj):
        visited = [0 for i in [0]*(n+1)]
        ans = 1
        for i in range(n+1):
            if visited[i]:
                continue
            Q = deque([i])
            temp = 1
            while Q:
                q = Q.popleft()
                visited[q] = 1
                link = adj[q]
                for j in link:
                    if visited[j]:
                        continue
                    visited[j] = 1
                    temp += 1
                    Q.append(j)
            ans = max(ans, temp)
        print(ans)  
    bfs(n, m, g)
 
if __name__=="__main__":
    main()

Measured memory_bytes: 46612
#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<algorithm>
using namespace std;
int GCD(int a,int b){
	if(!b)
		return a;
	return GCD(b,a%b);
}
int main(){
	int x;
	scanf("%d",&x);
	printf("%d\n",x*360/GCD(x,360)/x);
}


Measured memory_bytes: 1732
import math
from collections import deque
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法1 - 貪欲法
"""
キューを使った貪欲法で間に合わせる。
que = [[ダメージ量,そのダメージがどこまで使えるか],...]
とすることにより、高速にダメージ管理をすることができる。
"""

que = deque()
ans = 0
dmg = 0

for i in range(n):
    while que:
        lim = que.popleft()
        if lst1[i][0] > lim[1]:
            dmg -= lim[0]
        else:
            que.appendleft(lim)
            break
    
    if lst1[i][1] > dmg:
        need = math.ceil((lst1[i][1]-dmg)/a)
        ans += need
        dmg += need*a
        que.append([need*a,lst1[i][0]+2*d])

print(ans)


Measured memory_bytes: 96088
/* ex4_2
   moka223711 */

#include <stdio.h>
#include <math.h>
#define PI 3.14159265358

int main(void){
    // 時針の長さがlenh[cm]、分針の長さがlenm[cm]である時計のhour時minute分における
    // 時針の先端と分針の先端の距離を求める
    
    double lenh, lenm, hour, minute, radh, radm, rad, ans;
    scanf("%lf %lf %lf %lf", &lenh, &lenm, &hour, &minute);
    
    // 針が12時を指しているときを0[rad]とする
    // 時針は12時間(12*60分)で一周するので、hour時minute分のとき
    // 時針の角度radhは、2*PIに(hour/12+minute/60/12)をかけたものになる
    // 分針は60分で一周するので、分針の角度radmは2*PIにminute/60をかけたものになる
    radh = 2 * PI * (hour + minute / 60) / 12;
    radm = 2 * PI * minute / 60;
    
    // なす角を知りたいのでPI(180°)より小さい方を選ぶ
    rad = (radh-radm < PI) ? radh-radm : radm-radh;
    
    // 余弦定理を用いて時針の先端と分針の先端の距離を求める
    ans = sqrt(pow(lenh, 2) + pow(lenm, 2) - 2*lenh*lenm*cos(rad));
    // 誤差は10^{-9}まで許されるので10^{-10}まで表示する
    printf("%.10lf", ans);
    
    return 0;
}


Measured memory_bytes: 2568
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define ii pair<int,int>
#define MAX 1000000007

using namespace std;


int main(void){
	int h,w;
	cin >> h >> w;
	int s[h][w];
	rep(i,h){
		rep(j,w){
			char work;
			cin >> work;
			if(work == '#')s[i][j] = 1;
			else s[i][j] = 0;
		}
	}

	bool flag = true;
	rep(i,h){
		rep(j,w){
			if(s[i][j] == 0)continue;
			bool tmp = false;
			if(i+1 < h && s[i+1][j] == 1)tmp=true;
			if(i-1 > -1 && s[i-1][j] == 1)tmp=true;
			if(j+1 < w && s[i][j+1] == 1)tmp=true;
			if(j-1 > -1 && s[i][j-1] == 1)tmp=true;
			if(!tmp)flag = false;
		}
	}

	if(flag) cout << "Yes" << endl;
	else cout << "No" <<endl;

	return 0;

}


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

int main() {
  string a,b;
  cin >> a>>b;
  if(a.at(0)==b.at(2)&&a.at(1)==b.at(1)&&a.at(2)==b.at(0))
    cout<<"YES"<<endl;
  else
    cout<<"NO"<<endl;
  
  

}



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

using namespace std;

typedef long long ll;

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

    int n;
    cin >> n;
    vector<ll> a(n);
    int ans = 0;
    for (auto &i : a)
    {
    	cin >> i;
    	while (i%2==0)
    		i/=2, ++ans;
    }

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;

namespace mp = boost::multiprecision;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 55;

int N, K;

template <typename T>
class Matrix {
public:
  Matrix(int r, int c) {
    mat.clear();
    for(int i = 0; i < r; i++) {
      mat.push_back(vector<T>());
      mat[i].resize(c);
    }
  }

  vector<T>& operator[] (int r) {
    return mat[r];
  }

  void print() const {
    for(int i = 0; i < mat.size(); i++) {
      for(int j = 0; j < mat[i].size(); j++) {
        cerr << mat[i][j] << " ";
      }
      cerr << endl;
    }
  }

  unsigned int getR() const {
    return mat.size();
  }

  unsigned int getC() const {
    return mat[0].size();
  }

  Matrix operator + (Matrix& matrix) {
    Matrix<T> ret(this->getR(), this->getC());
    for(int r = 0; r < matrix.getR(); r++) {
      for(int c = 0; c < matrix.getC(); c++) {
        ret[r][c] = (*this)[r][c] + matrix[r][c];
        ret[r][c] %= MOD;
      }
    }
    return ret;
  }

  void operator += (Matrix& matrix) {
    for(int r = 0; r < matrix.getR(); r++) {
      for(int c = 0; c < matrix.getC(); c++) {
        (*this)[r][c] += matrix[r][c];
        (*this)[r][c] %= MOD;
      }
    }
  }

  Matrix operator * (Matrix& matrix) {
    Matrix<T> ret(this->getR(), matrix.getC());
    for(int r = 0; r < getR(); r++) {
      for(int c = 0; c < matrix.getC(); c++) {
        for(int rr = 0; rr < matrix.getR(); rr++) {
          ret[r][c] += (*this)[r][rr] * matrix[rr][c];
          ret[r][c] %= MOD;
        }
      }
    }
    return ret;
  }

  void operator *= (Matrix& matrix) {
    (*this) = (*this) * matrix;
  }

private:
  vector<vector<T>> mat;
};

signed main()
{
  cin >> N >> K;
  Matrix<int> mat(N, N), tmp(N,N);

  REP(i,N) {
    REP(j,N) {
      cin >> mat[i][j];
    }
    tmp[i][i] = 1;
  }

  Matrix<int> initMat(1, N);
  REP(i,N) {
    initMat[0][i] = 1;
  }

  while(K) {
    if(K&1)
      tmp *= mat;
    
    mat *= mat;
    K /= 2;
  }

  initMat *= tmp;

  int ans = 0;
  REP(n,N) {
    ans += initMat[0][n];
    ans %= MOD;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B;
    cin >> A >> B;
    if(A * B % 2 == 1) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,b,e) for(int i=(b);i<(e);++i)
#define RREP(i,b,e) for(int i=(b)-1;i>=e;--i)
#define rep(i,e) for(int i=0;i<(e);++i)

inline void print(void) { cout<<'\n'; }
template<class T> inline void print(const T &x) { cout<<x<<'\n'; }
template<class T, class... U> inline void print(const T &x, const U&... y) { cout<<x<<" "; print(y...); }

int main() {
  int n; cin>>n;
  vector<int> a(n);
  rep(i, n) cin>>a[i];
  sort(a.begin(), a.end(), [](auto x, auto y){ return abs(x) > abs(y); });

  bool good = true;
  rep(i, n) if (a[i] < 0) good = !good;

  long long ans = 0;
  if (good) rep(i, n) ans += abs(a[i]);
  else {
    rep(i, n-1) ans += abs(a[i]);
    ans -= abs(a[n-1]);
  }
  print(ans);

  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
using ui64 = uint_fast64_t;
#define REP(i, n) for (i64 (i) = 0; (i) < (n); ++(i))
#define FOR(i, a, b) for (i64 (i) = (a); (i) < (b); ++(i))

int N, M;
vector<vector<int>> graph;
vector<double> dp, dp2;

double rec(int cur) {
    if (dp[cur] != -1) return dp[cur];
    if (cur == N - 1) return dp[cur] = 0.0;
    double ret = 0.0;
    int cnt = 0;
    for (auto& nxt: graph[cur]) {
        ++cnt;
        ret += rec(nxt);
    }
    ret /= cnt;
    return dp[cur] = ret + 1.0;
}

double rec2(int cur, int idx) {
    if (dp2[cur] != -1) return dp2[cur];
    if (cur == N - 1) return dp2[cur] = 0.0;
    if (cur != idx) {
        double ret = 0.0;
        int cnt = 0;
        for (auto& nxt: graph[cur]) {
            ++cnt;
            ret += rec2(nxt, idx);
        }
        ret /= cnt;
        return dp2[cur] = ret + 1.0;
    } else {
        int idx = 0;
        double mx = 0.0, ret = 0.0;
        int cnt = 0;
        for (auto& nxt: graph[cur]) {
            ++cnt;
            double tmp = rec2(nxt, idx);
            if (mx < tmp) {
                mx = tmp;
                idx = nxt;
            }
            ret += tmp;
        }
        ret -= mx;
        ret /= cnt - 1;
        return dp2[cur] = ret + 1.0;
    }
}

signed main() {

    cin >> N >> M;

    graph.assign(N, vector<int>());
    REP(i, M) {
        int S, T;
        cin >> S >> T;
        --S, --T;
        graph[S].emplace_back(T);
    }

    dp.assign(N, -1);
    rec(0);

    double ret = dp[0];

    REP(i, N) {
        if (graph[i].size() == 1) continue;
        dp2.assign(N, -1);
        rec2(0, i);
        ret = min(ret, dp2[0]);
    }

    cout << setprecision(15) << ret << endl;

}

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

using namespace std;
#define rep(i, s, n) for(int i = s;i<n;i++)

int main(void) {
    int x;
    cin >> x;
    if (x == 7 || x == 5 || x == 3) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug1: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug2: "<<x<<" "<<y<<endl;
#define bug3(x, y, z) cout<<"zdongdebug3: "<<x<<" "<<y<<" "<<z<<endl;
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int mod = 1000000007;


int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  int n;
  bool sign = 0;
  cin>>n;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    if(x%2==0&&!(x%5==0||x%3==0))sign=1;
  }
  if(sign)cout<<"DENIED"<<endl;
  else cout<<"APPROVED"<<endl;
  return 0;
}

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

 int main() {
 int N;
 cin >> N;
 vector<int> a(N);
int sum = 0;

 for (int i = 0; i < N; ++i) {
 cin >> a[i];
 sum += a[i];
 }

 int mini = sum;
 int prefix_sum = 0;
 for (int i = 0; i < N; ++i) {
 cin >> a[i];
 prefix_sum += a[i];
 mini = min(mini, abs(prefix_sum - (sum - prefix_sum)));
 }

 cout << mini << endl;
 return 0;
 }


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static readonly long Mod = 1000000000 + 7;

        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var S = ReadLine();
            var ans = 0;
            var pre = string.Empty;
            var i = 0;
            while (i < S.Length)
            {
                if (pre.Length == 1 && pre[0] == S[i])
                {
                    if (i == S.Length - 1) break;
                    pre = S.Substring(i, 2);
                    ++i;
                }
                else
                    pre = S[i].ToString();
                ++ans;
                ++i;
            }
            WriteLine(ans);
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 15712
import sys
import math
import bisect

def main():
    n = int(input())
    A = list(map(int, input().split()))
    ans = 0
    for i in range(1, n - 1):
        if A[i] == sorted([A[i-1], A[i], A[i+1]])[1]:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()


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

int main(){
	int k,a,b;
	cin >> k >> a >> b;

	k = b/k*k;
	if(a<=k)
		cout << "OK" << endl;
	else
	{
		cout << "NG" << endl;
	}
	
}

Measured memory_bytes: 3600
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    int[][] bingo = new int[3][3];
    String[] line;
    
    for(int i=0; i<3; i++){
      line = br.readLine().split(" ");
      for (int j=0; j<3; j++){
        bingo[i][j] = Integer.parseInt(line[j]);
      }
    }
    int n = Integer.parseInt(br.readLine());
    int num;
    for (int i=0; i<n; i++){
      num = Integer.parseInt(br.readLine());
      for (int j=0; j<3; j++){
        for (int k=0; k<3; k++){
          if (bingo[j][k] == num) bingo[j][k] = 0;
        }
      }
    }
    for (int i=0; i<3; i++){
      if (bingo[i][0] == bingo[i][1] && bingo[i][1] == bingo[i][2] && bingo[i][0] == 0){
        System.out.println("Yes");
        return;
      }
      if (bingo[0][i] == bingo[1][i] && bingo[1][i] == bingo[2][i] && bingo[0][i] == 0){
        System.out.println("Yes");
        return;
      }
    }
    if (bingo[0][0] == 0 && bingo[1][1] == 0 && bingo[2][2] == 0 ||
    bingo[0][2] == 0 && bingo[1][1] == 0 && bingo[2][0] == 0){
      System.out.println("Yes");
      return;
    }
    System.out.println("No");
  }
}

Measured memory_bytes: 23252
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;

int main(){
    int wb = 0, bw = 0;
    string s;
    cin>>s;
    int n = s.size();
    int guki = 0;
    int guki2 = 0, i;
    for(i = 0; i<n; i++){
        if(s[i] == '0' && guki == 0){
            wb++;
        }
        else if(s[i] == '1' && guki == 1){
            wb++;
        }
        if(s[i] == '1' && guki2 == 0){
            bw++;
        }
        else if(s[i] == '0' && guki2 == 1){
            bw++;
        }
        if(guki == 0){
            guki++;
        }
        else{
            guki = 0;
        }
        if(guki2 == 0){
            guki2++;
        }
        else{
            guki2 = 0;
        }
    }

    if(bw<wb){
        cout<<bw<<endl;
    }
    else{
        cout<<wb<<endl;
    }
   
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;(i)--)
#define rrep1(i,n) for(int i=((int)(n));i>0;(i)--)
#define sz(c) ((int)(c).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> P;
typedef pair<int, pair<int, int> > PP;
//const int MAX=;

int A,B;
void input(){
    cin>>A>>B;
    int ans=max(A+B, A-B);
    ans=max(ans, A*B);
    cout<<ans<<endl;

}

void solve(){

}

void output(){
  
}

int main(){
  input();
  solve();
  output();
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    while(1)
    {
        int a, b;
        
        cin >> a >> b;
        
        if(a == 0 || b == 0)
        { break; }
        
        for(int i = 0; i < a; ++i)
        {
            for(int j = 0; j < b; ++j)
            {
                if ( (i % 2) == 0)
                {
                    if( j % 2 == 0)
                    { cout << "#"; }
                    else 
                    { cout << ".";}
                }
                else 
                {
                    if( j % 2 == 0)
                    { cout << ".";  }
                    else 
                    { cout << "#";  }
                    
                    
                }
            }
            cout << endl;
            
        }
        
        cout << endl;
        
    }
    
    return 0;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
ll mod = 1e9 + 7;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;cin>>n>>m;
	set<int>s;
	for(int i = 0; i < n; ++i){
		int t;cin>>t;
		s.insert(t);
	}
	int dp[n+1];
	dp[0] = 1;
	dp[1] = (s.find(1)==s.end()?1:-1);
	for(int i = 2; i<=n; ++i){
		dp[i] = 0;
		if(s.find(i)!=s.end()){
			dp[i] = -1;
			continue;
		}
		if(dp[i-1]!=-1){
			dp[i] += dp[i-1];
		}
		if(dp[i-2]!=-1){
			dp[i] += dp[i-2];
		}
		dp[i]%=mod;
	}
	cout<<dp[n]<<endl;
	return 0;
}



Measured memory_bytes: 5376
import sys
input=sys.stdin.readline

import heapq

def dijkstra(s,edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

n,m,s,t=map(int,input().split())
s,t=s-1,t-1
edge1=[[] for _ in range(n)]
edge2=[[] for _ in range(n)]
for _ in range(m):
  u,v,a,b=map(int,input().split())
  edge1[u-1].append([a,v-1])
  edge1[v-1].append([a,u-1])
  edge2[u-1].append([b,v-1])
  edge2[v-1].append([b,u-1])
d1=dijkstra(s,edge1)
d2=dijkstra(t,edge2)
INF=10**15
ans=[INF]*n
ans[n-1]=int(d1[n-1]+d2[n-1])
for i in range(n-2,-1,-1):
  tmp=int(d1[i]+d2[i])
  ans[i]=min(tmp,ans[i+1])
for i in range(n):
  print(INF-ans[i])

Measured memory_bytes: 96588
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
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; }
const long double PI = acos(-1.0);
// cout << fixed << setprecision(14);
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int a;
	cin >> a;
	cout << a + a*a + a*a*a << endl;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
#include <string>
#define rep(i, k) for(int i = 0; i < (k); i++)

using namespace std;

int main(void)
{
    int N;
    cin >> N;
    vector<int> v(N);
    rep(i, N)cin >> v[i];

    sort(v.begin(), v.end());

    double ans = v[0];
    for(int i = 1; i < N; i++){
        ans += v[i];
        ans /= 2;
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define int long long
using namespace std;
const int MOD=1e9+7;
const int INF=1e10;
template<typename T> void cmax(T &a, T b) {a = max(a, b);}
template<typename T> void cmin(T &a, T b) {a = min(a, b);}

signed main(){
  vector<int> a(3);
  rep(i,3)cin>>a[i];
  sort(all(a));
  int ans=0;
  rep(i,2){
    ans+=abs(a[i]-a[i+1]);
  }
  cout<<ans<<endl;
  return 0;
}


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

int main()
{
	int n;
	double w, h;
	
	while (scanf("%d,%lf,%lf", &n, &w, &h) != EOF){
		if (w / (h * h) >= 25.0){
			cout << n << endl;
		}
	}
	
	return (0);
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int (i)=(a);(i)<(int)(b);(i)++)
#define RREP(i,a,b) for(int (i)=(a);(i)>=(int)(b);(i)--)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;

int cnt[3];

int main(){
    int n;
    cin >> n;
    REP(i,0,n){
        int a;
        cin >> a;
        if (a % 2) cnt[0]++;
        else if (a % 4) cnt[1]++;
        else cnt[2]++;
    }
    
    if (cnt[1] == 0) cout << (cnt[0] <= cnt[2] + 1?"Yes":"No") << endl;
    else cout << (cnt[0] <= cnt[2]?"Yes":"No") << endl;
    return 0;
}

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




typedef long long ll;
ll N;
ll A[101010];
//-----------------------------------------------------------------
ll d[101010];
ll r[101010];
bool sol() {
	if (N == 1) return true;
	if (N == 2) {
		int mi = min(A[0], A[1]);
		int ma = max(A[0], A[1]);

		return ma == mi * 2;
	}

	rep(i, 0, N) {
		int j = (i + 1) % N;
		d[i] = A[j] - A[i];
	}

	ll n = -(1LL << 60);
	rep(i, 0, N) n = max(n, d[i]);
	if (n < 0) return false;

	ll a = N * (N - 1) / 2;

	if (n == 0) {
		rep(i, 0, N) if (d[i] != 0) return false;
		rep(i, 0, N) if (A[i] % a) return false;
		return true;
	}

	ll sm = 0;
	rep(i, 0, N) {
		ll up = n - d[i];
		if (up < 0) return false;
		if (up % N) return false;

		sm += up / N;
		r[i] = up / N;
	}

	if (sm != n) return false;

	// r[i]回r[i+1]から足し始めている
	ll a0 = 0;
	rep(i, 0, N) {
		a0 += r[i] * (N - i);
	}
	
	return (A[0] - a0) % a == 0;
}
//-----------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, N) scanf("%lld", &A[i]);

	if (sol())
		printf("YES\n");
	else
		printf("NO\n");
}

Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<algorithm>
#include <iterator>
#include<queue>
#include <string>
#include <numeric>
#include<stack>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) v.begin(),v.end()
struct AboutTo{
	int time;
	int toid;
};
struct Node{
	int id;
	vector<AboutTo> ToCole;
};
vector<Node> FinishedNodeCole;
vector<Node> NodeCole;
struct a{
	int time;
	int toid;
};
bool operator < (a aNode,a bNode){
	return aNode.time > bNode.time;
}
priority_queue<a> Npq;

int daikusutora(vector<int> aTimeCole){
	int amax=0;
	while (!Npq.empty()){
		
		a apair = Npq.top();
		Npq.pop();
		int aid = apair.toid;
		int atime = apair.time;
		for (auto it : NodeCole[aid].ToCole){
			if (atime+it.time > aTimeCole[it.toid]){
				Npq.push({ atime + (it).time, (it).toid });
				aTimeCole[it.toid] = atime+it.time;
				amax = max(amax, atime+it.time);
			}
		}

	}

	return amax;
}

int main(){
	int n, m;
	cin >> n >> m;
	vector<int>TimeCole(n);
	REP(i, n){
		NodeCole.push_back({ i, {} });
	}
	REP(i, m){
		int a, b, c;
		cin >> a >> b >> c;
		NodeCole[a].ToCole.push_back({ c, b });
	//	NodeCole[b].RestTimeCole.push_back(9999);
	}
	//NodeCole[0].aRestTime = 0;

	//FinishedNodeCole.push_back(NodeCole[0]);
	Npq.push({ 0, 0 });
	cout<<daikusutora(TimeCole)<<endl;

	return 0;
}
	

Measured memory_bytes: 1252
// AtCoder178.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    cin >> s;

    int i = atoi(s.c_str());
    if (i == 0) {
        cout << 1;
    }
    else {
        cout << 0;
    }
    return 0;
}



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

int main() {
  int n,cnt=1;
  cin>>n;
  rep(i,n){
    int a;
    cin>>a;
    if(a%2==0){
      cnt*=2;
    }
  }
  cout<<pow(3,n)-cnt<<endl;
}
  

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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

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

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

	vi x(n);
	int ans=0;
	for (int i = 0; i < n; i++){
		cin>>x[i];
	}
	for (int i = 0; i < n; i++){
		if(x[i]==i+1){
			ans++;
			swap(x[i],x[i+1]);
		}
	}

	cout<<ans<<endl;


	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using psi=pair<string,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9
#define MOD ((ll)1e9+7)
void get(){}template<class H,class...T>void get(H&h,T&...t){cin>>h;get(t...);}
template<class T>void geti(T&a){for(auto&_:a)cin>>_;}
template<class T>void getii(T&a){for(auto&_:a)geti(_);}
void put(string d){}template<class H,class...T>void put(string d,H&h,T&...t){cout<<h;if(sizeof...(t))cout<<d;put(d,t...);}
template<class T>void puti(T&a,string d=" "){bool f=1;for(auto&_:a)cout<<(exchange(f,0)?"":d)<<_;cout<<endl;}
template<class T>void putii(T&a,string d=" "){for(auto&_:a)puti(_,d);}
#define dcl(...) ll __VA_ARGS__;get(__VA_ARGS__)
#define dclt(t,...) t __VA_ARGS__;get(__VA_ARGS__)
template<class F,class S>void add(map<F,S>&mp,F f,S s){if(mp.find(f)==mp.end())mp[f]=F();mp[f]+=s;}
 
int main(){
    int h,v;
    using data=pair<int,int>;
    
    while(cin>>h>>v, h or v){
        int tv[]={-3,-1,1,3};
        int tc[]={v,h,h,v};
        int p10[]={100000000,10000000,1000000,100000,10000,1000,100,10,1};
        array<int,9> a,b;
        geti(a);
        geti(b);
        int sa=0,sb=0;
        for(auto i:a)sa=sa*10+i;
        for(auto i:b)sb=sb*10+i;
    
        unordered_map<int,int> s;

        priority_queue<data> q;
        q.emplace(0,sa);
        
        while(1){
            int cost=q.top().fs;
            int board=q.top().sc;
            q.pop();
            if(board==sb){
                cout<<-cost<<endl;
                break;
            }
            int index=to_string(board).find('0');
            if(index==-1)index=0;
            rep(i,4){
                int fixed=(index+tv[i]+9)%9;
                int next=board;
                int fx=next/p10[fixed]%10;
                next-=p10[fixed]*fx;
                next+=p10[index]*fx;
                if(s.find(next)==s.end() || (s[next]<cost-tc[i] && cost-tc[i]>-8000)){
                    q.emplace(cost-tc[i], next);
                    s[next]=cost-tc[i];
                }
            }
        }
    }
}



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

using ll = long long;

const ll INF = 1e18 + 1;

// dynamic programming approach
ll knapsack(vector<pair<ll, int>> &wv, ll  w, ll sum_val){
    // dp[i] represents the minimum weight which can be formed by value i
    vector<ll> dp(sum_val + 1, INF);
    dp[0] = 0;

    for(int items = 0;items < wv.size();items++){
        for(int value_already = sum_val - wv[items].second;value_already >= 0;value_already--){
            dp[value_already + wv[items].second] = min(dp[value_already + wv[items].second], dp[value_already] + wv[items].first);
        }
    }

    ll ans = 0;
    
    for(int i = 0;i < dp.size();i++){
        if(dp[i] <= w)
            ans  = max(ans, (ll) i);
    }

    return ans;
}

int main(){
    ll n, w;
    ll sum_val = 0;
    cin >> n >> w;
    vector<pair<ll, int>> wv(n);

    for(int i = 0;i < n;i++){
        cin >> wv[i].first >> wv[i].second;
        sum_val += wv[i].second;
    }

    cout << knapsack(wv, w, sum_val) << endl;

    return 0;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  while (true) {
    int n, l, r;
    cin >> n >> l >> r;
    if (n + l + r == 0) return 0;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a.at(i);
    
    int ans = 0;
    for (int i = l; i <= r; i++) {
      bool flag = false;
      for (int j = 0; j < n; j++) {
        if (i % a.at(j) == 0 && j % 2 == 0) {
          ans++;
          flag = true;
          break;
        }
        else if (i % a.at(j) == 0) {
          flag = true;
          break;
        }
      }
      if (!flag) {
        if (n % 2 == 0) ans++;
      }
    }
    
    cout << ans << '\n';
  }
}


Measured memory_bytes: 3172