Skip to content

Instantly share code, notes, and snippets.

View knuu's full-sized avatar

knuu knuu

View GitHub Profile
@knuu
knuu / yuki177.py
Created October 15, 2016 11:43
yukicoder No.177 制作進行の宮森あおいです!
import collections
class MaxFlow:
"""Dinic Algorithm: find max-flow
complexity: O(EV^2)
used in GRL6A(AOJ)
"""
class Edge:
def __init__(self, to, cap, rev):
@knuu
knuu / Gperm.py
Created August 12, 2016 12:17
SRM696 div.1 300 Gperm その2
# -*- coding: utf-8 -*-
class Gperm:
def countfee(self, x, y):
range = xrange
N, E = 50, len(x)
INF = 10**9
dp = [INF] * (1 << E)
dp[0] = 0
edge = [0] * N
# 各頂点を塗りつぶさない状態にしたときにコストがかからなくなる枝集合を計算
@knuu
knuu / Gperm.cpp
Created August 12, 2016 12:14
SRM696 div.1 300 Gperm その1
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
struct Gperm {
vector<int> x, y;
int countfee(vector<int> _x, vector<int> _y) {
@knuu
knuu / cdf367_2d.cpp
Last active August 11, 2016 19:53
Codeforces Round #367 (div. 2) D. Vasiliy's Multiset
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
int main() {
int Q; scanf("%d", &Q);
map<int, int> mult;
mult[0]++;
@knuu
knuu / cdf367_2c.cpp
Last active October 15, 2016 16:41
Codeforces Round #367 (div. 2) C. Hard problem
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
int main() {
int N; cin >> N;
vector<ll> C(N); REP(i, N) cin >> C[i];
@knuu
knuu / cdf367_2b.cpp
Last active August 11, 2016 19:59
Codeforces Round #367 (div. 2) B. Interesting drink
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
int main() {
int N; scanf("%d", &N);
vector<int> X(N); REP(i, N) scanf("%d", &X[i]);
@knuu
knuu / cdf367_2a.py
Created August 11, 2016 19:46
Codeforces Round #367 (div. 2) A. Beru-taxi
from math import hypot
a, b = map(int, input().split())
n = int(input())
ans = 10**6
for _ in range(n):
x, y, v = map(int, input().split())
ans = min(ans, hypot(x-a, y-b)/v)
print('{:.20f}'.format(ans))
@knuu
knuu / tkppc_d.py
Created August 8, 2016 22:34
技術室奥プログラミングコンテスト#2 D - エンブレム(Emblem)
from fractions import gcd
H, W, K = map(int, input().split())
g = gcd(K, W)
W, K = W//g, K//g
print(K//2*W//2+(K-1)//2*(W-2)//2)
@knuu
knuu / abc041_d.nim
Created July 2, 2016 14:11
AtCoder Beginner Contest #041 D
import strutils, sequtils
let
tmp = stdin.readline.split.map(parseInt)
(N, M) = (tmp[0], tmp[1])
var edge = newSeqWith(N, newSeq[int]())
for _ in 1..M:
let
e = stdin.readline.split.map(parseInt)
(s, t) = (e[0]-1, e[1]-1)
edge[t].add(s)
@knuu
knuu / abc041_c.nim
Created July 2, 2016 14:10
AtCoder Beginner Contest #041 C
import strutils, algorithm, sequtils
let
N = stdin.readline.parseInt
A = stdin.readline.split.map(parseInt)
var students = newSeq[(int, int)](N)
for i, a in A: students[i] = (a, i+1)
students.sort(cmp)
for student in students.reversed:
student[1].echo